[알고리즘 PS] 백준 14502번 연구소 자바 문제풀이

문제

해당 포스팅은 백준의 백준 14502번 연구소 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

14502번: 연구소

 

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

 

문제 접근

 

이 문제는 DFS와 BFS 를 모두 이용하는 것이 가장 편하다.

 

벽을 세우는 것을 DFS 를 이용하면 되고, 바이러스를 퍼트리는 것을 BFS 로 이용할 수 있다.

 

정답 코드

public class Main {

    private static int n;
    private static int m;
    private static int[][] arr;
    private static int[][] temp;
    private static int answer = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nm = br.readLine().split(" ");

        n = Integer.parseInt(nm[0]); // y
        m = Integer.parseInt(nm[1]); // x

        arr = new int[n][m];
        temp = new int[n][m];

        for (int i = 0; i < n; i++) {
            String[] s = br.readLine().split(" ");

            for (int j = 0; j < s.length; j++) {
                arr[i][j] = Integer.parseInt(s[j]);
            }
        }

        // 반복 돌면서 setWall() 함수 호출

        // bfs 로 바이러스 퍼트리기
        setWall(0);

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
    }

    private static void setWall(int depth) {
        if(depth == 3) {
            spread();
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                if(arr[i][j] == 0) {
                    arr[i][j] = 1;
                    setWall(depth + 1);
                    arr[i][j] = 0;
                }
            }
        }
    }

    private static void spread() {


        Queue<Position> queue = new LinkedList<>();

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[i].length; j++) {
                temp[i][j] = arr[i][j];
            }
        }

        for (int i = 0; i < temp.length; i++) {
            for (int j = 0; j < temp[i].length; j++) {
                if (temp[i][j] == 2) {
                    queue.add(new Position(j, i));
                }
            }
        }

        int[] xPos = {1, -1, 0, 0};
        int[] yPos = {0, 0, 1, -1};


        while(!queue.isEmpty()) {
            Position front = queue.remove();

            for (int i = 0; i < 4; i++) {
                int xx = front.x + xPos[i];
                int yy = front.y + yPos[i];

                if(0 <= xx && xx < m && 0 <= yy && yy < n) {
                    if (temp[yy][xx] == 0) {
                         temp[yy][xx] = 2;
                         queue.add(new Position(xx, yy));
                    }
                }
            }
        }

        answer = Math.max(answer, countSafetyZone());
    }

    private static int countSafetyZone() {
        int count = 0;

        for (int i = 0; i < temp.length; i++) {
            for (int j = 0; j < temp[i].length; j++) {
                if(temp[i][j] == 0) count++;
            }
        }
        return count;
    }

    private static class Position {
        int x;
        int y;
        public Position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.