[백준] 14502번: 연구소 - java

문제

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

접근법

세로와 가로 크기가 최대 8이기 때문에 3중 for문을 사용해 벽의 위치를 선택해도 된다. 나는 for문이 아니라 재귀 함수를 사용했다. 3개의 벽 위치가 다 정해졌으면 BFS를 사용해 바이러스를 퍼트리고, 바이러스가 다 퍼진 후에는 안전 영역의 개수를 세어 현재 최댓값과 비교했다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.List;

public class Main {

    static int N, M;
    static int[][] map;
    static boolean[][] visited;
    static List<Point> virus = new ArrayList<>();
    static int answer = 0;

    static int[] dirR = {-1, 1, 0, 0};
    static int[] dirC = {0, 0, -1, 1};

    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());

        map = new int[N][M];
        visited = new boolean[N][M];

        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());

                // 바이러스 위치를 리스트에 저장한다.
                if (map[i][j] == 2) {
                    virus.add(new Point(i, j));
                }
            }
        }

        DFS(new Point(0, 0), 0);
        System.out.println(answer);
    }

    private static void DFS(Point p, int cnt) {
        // 3개의 벽을 모두 세운 경우
        if (cnt == 3) {
            int tmp = BFS();
            answer = Math.max(answer, tmp);
            return;
        }

        for (int i = p.r; i < N; i++) {
            for (int j = (i == p.r ? p.c : 0); j < M; j++) {
                if (map[i][j] == 0 && !visited[i][j]) {
                    visited[i][j] = true;
                    map[i][j] = 1;
                    DFS(new Point(i, j), cnt + 1);
                    visited[i][j] = false;
                    map[i][j] = 0;
                }
            }
        }
    }

    private static int BFS() {
        boolean[][] infected = new boolean[N][M];
        Deque<Point> queue = new ArrayDeque<>();

        for (Point p : virus) {
            queue.offer(p);
            infected[p.r][p.c] = true;
        }

        while (!queue.isEmpty()) {
            Point now = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nextR = now.r + dirR[i];
                int nextC = now.c + dirC[i];

                if (rangeIn(nextR, nextC) && map[nextR][nextC] == 0 && !infected[nextR][nextC]) {
                    infected[nextR][nextC] = true;
                    queue.offer(new Point(nextR, nextC));
                }
            }
        }

        // 안전 구역 갯수 구하기
        int cnt = 0;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < M; c++) {
                if (!infected[r][c] && map[r][c] == 0) {
                    cnt++;
                }
            }
        }

        return cnt;
    }

    private static boolean rangeIn(int r, int c) {
        return (r >= 0) && (c >= 0) && (r < N) && (c < M);
    }

    static class Point {
        int r, c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
}

 

주의할 점

재귀 함수의 for문 범위를 정할 때 처음에는 아래와 같이 작성하였다.

for (int i = p.r; i < N; i++) {
	for (int j = p.c; j < M; j++) {
    	...
    }
}

이렇게 범위를 지정하게 되면 아래 사진에서 우리가 탐색하고자 하는 범위는 왼쪽이지만, 오른쪽 범위에서 탐색하게 된다. 따라서 j의 범위 (열 범위)를 삼항 연산자를 사용해 계산해주었다.