[백준 14502] 연구소 - 자바(java)

 

0은 빈칸, 1은 벽, 2는 바이러스 이고 N과 M으로 이루어진 지도 안에서 벽을 3개 세워서 나올 수 있는 최대 안전 영역의 크기를 구해야한다.

 

N과 M이 8이므로 완전 탐색으로 구해도 시간이 남을 것 같다라는 생각을 하였고, 벽을 3개 나눈 것 또한 백트래킹을 통해 벽을 세우고 BFS를 통하여 바이러스를 퍼뜨리고 각각의 경우에 대하여 안전 영역을 구하도록 하면 될 것 같다라고 생각했다.

 

벽을 3개 나누는 백트래킹은 

백준 N과 M(5) 에서 사용한 백트래킹을 사용하였다.

 

그러면 내가 구현해야할 알고리즘은 벽 3개를 세울 dfs(백트래킹) 알고리즘, 바이러스를 퍼뜨릴 BFS 알고리즘, 바이러스를 퍼뜨리고 남은 안전영역을 구하는 브루트포스 알고리즘

이렇게 3개가 있는 것 같다. 각각의 메소드로 따로따로 구현해보도록 하겠다.

 

static

    static int[] dx = {-1, 1, 0, 0}; //directX (x가 움직일 방향)
    static int[] dy = {0, 0, -1, 1};//direcY (y가 움직일 방향)
    static int N, M, max; // N, M , max 는 정답

    static int[][] graph; //원래 graph 저장
    static int[][] copyGraph; // 벽을 세우고 bfs를 할 copy한 graph값 
    static ArrayList<int[]> list = new ArrayList<>(); // 백트래킹을 위한 빈칸을 저장하기 위한 ArrayList

 

일단 method가 3개이므로 필요한 static 값도 많다.

 

방향과, N과  M 그리고 안전영역 최대값

graph 값 그리고 bfs를 백트래킹에서 나온 경우의 수만큼 돌릴 것이기 때문에 graph를 보존하기 위한 copyGraph

그리고 백트래킹을 위한 빈칸 저장 arrayList 

 

main 

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        graph = new int[N][M];
        copyGraph = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int a = Integer.parseInt(st.nextToken());
                graph[i][j] = a;
                if (a == 0) {
                    list.add(new int[]{i, j});
                }
            }
        }
        dfs(0, 0, new int[3][2]);
        System.out.println(max);
    }

메인에서 N과 M을 구하고 graph와 copGraph 다 선언 해주고

0 (빈칸) 일 경우 list에 넣어주고 

dfs를 돌린다.

 

DFS (백트래킹)

public static void dfs(int depth, int seq,int[][] canWall) {
    if (depth == 3) {
        for (int i = 0; i < N; i++) {
            copyGraph[i] = graph[i].clone();
        }
        for (int i = 0; i < 3; i++) {
            int[] wall = canWall[i];
            copyGraph[wall[0]][wall[1]] = 1;
        }
        bfs();

        return;
    }
    for (int i = seq; i < list.size(); i++) {
        canWall[depth] = list.get(i);
        dfs(depth + 1, i + 1, canWall);
    }
}

depth가 3이 넘어가면 graph를 copy 후 백트래킹을 통해 구한 3개의 벽을 교체한 후 bfs로 보낸다

 

겹치지 않는 값만 해서 벽이 될 수 있는 값을 구한 후 하는 백트래킹 

자세한 구조는 백준 N과 M(5) 여기서 이해하시면 좋을 것 같습니다!

 

BFS

public static void bfs() {
    Queue<int[]> queue = new ArrayDeque<>();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (graph[i][j] == 2) {
                queue.add(new int[]{i, j});
            }
        }
    }

    while (!queue.isEmpty()) {
        int[] cur = queue.poll();
        for (int i = 0; i < 4; i++) {
            int nx = cur[0] + dx[i];
            int ny = cur[1] + dy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            if(copyGraph[nx][ny] !=0) continue;

            queue.add(new int[]{nx, ny});
            copyGraph[nx][ny] = 2;
        }
    }
    max = Math.max(remain(), max);
}

for문을 돌면서 2(바이러스) 인 곳은 queue에 집어넣은 후 

 

queue가 빌 때까지 bfs를 돌면서 visit으로 방문을 구하는 것이 아닌 0(빈칸) 이 아닌 경우에만 continue할 수 있도록 하였다.

바이러스가 옮겨 가면 옮겨간 좌표는 2(바이러스)로 바꾼다.

 

while문이 끝나고 모든 바이러스가 전염 되었다면 

remain으로 남은 값을 구하구, max와 비교해서 max값을 구한다!!

 

브루트포스

public static int remain() {
    int ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (copyGraph[i][j] == 0) {
                ans++;
            }
        }
    }
    return ans;
}

지금까지 구현한것 중 제일 쉬운 알고리즘

이중 for문으로 돌면서 0인 개수를 세고 난 후 값을 반환한다

 

 

답

import java.util.*;
import java.io.*;

public class Main {
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int N, M, max;

    static int[][] graph;
    static int[][] copyGraph;
    static ArrayList<int[]> list = new ArrayList<>();
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        graph = new int[N][M];
        copyGraph = new int[N][M];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                int a = Integer.parseInt(st.nextToken());
                graph[i][j] = a;
                if (a == 0) {
                    list.add(new int[]{i, j});
                }
            }
        }
        dfs(0, 0, new int[3][2]);
        System.out.println(max);
    }

    public static void dfs(int depth, int seq,int[][] canWall) {
        if (depth == 3) {
            for (int i = 0; i < N; i++) {
                copyGraph[i] = graph[i].clone();
            }
            for (int i = 0; i < 3; i++) {
                int[] wall = canWall[i];
                copyGraph[wall[0]][wall[1]] = 1;
            }
            bfs();

            return;
        }
        for (int i = seq; i < list.size(); i++) {
            canWall[depth] = list.get(i);
            dfs(depth + 1, i + 1, canWall);
        }
    }

    public static void bfs() {
        Queue<int[]> queue = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (graph[i][j] == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if(copyGraph[nx][ny] !=0) continue;

                queue.add(new int[]{nx, ny});
                copyGraph[nx][ny] = 2;
            }
        }
        max = Math.max(remain(), max);
    }

    public static int remain() {
        int ans = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (copyGraph[i][j] == 0) {
                    ans++;
                }
            }
        }
        return ans;
    }
}

 

시간초과에 많이 대여서 이렇게 구현해도 되려나 싶었는데, 8까지 밖에 없어서 그런지 이런식으로 구해도 답은 나왔다! 다음에 만약 이런 문제가 나왔을 경우에는 시간을 좀 더 단축할만한 방법을 찾아야겠다.