[BFS] 백준 14502번 : 연구소 - Java

2025/2/24(월)

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

벽을 어떻게든 가장 효율적으로 둬서 0의 개수를 최대한 많이 남겨야한다!

벽을 세우는 방법을 알아서 생각해야된다.

 

[접근 방법]

벽을 어떻게 하면 효율적으로 세울 수 있을까?

완전탐색으로 벽까지도 모든 경우의 수를 다 채워봐야한다.

시간초과가 나지 않을까하는 불안이 있었지만 문제에서 주어진 조건인 세로 N, 가로 M 크기가 작다. 또한, 문제에서 시간 제한은 2초

그래서 모든 벽을 세우는 경우는 64 x 64 x 64 = 1670만개 밖에 안 나온다. (새로 세울 수 있는 벽은 3개이며, 꼭 3개를 세워야한다)

 

너비 우선 탐색을 돌리면서 그 때 0의 개수를 세면 된다. 모든 경우의 수에 대해 0의 개수가 가장 많은 것을 출력하면 정답!

 

이번 문제에서 방문 체크 배열을 두지 않는 이유

-> 바이러스가 있는 곳은 2로 채우고, 0인 곳만 퍼져나가게 한다. 바이러스가 이미 퍼진 곳은 0에서 2로 바꾼다.

 

[풀이]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.StringTokenizer;

// 골드 4 - BFS
public class Main {

    private static final int[] rx = {0, 0, 1, -1};
    private static final int[] ry = {1, -1, 0, 0};

    private static class Node {
        int r, c;

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

    private static int[][] map;
    private static int N, M;
    private static ArrayDeque<Node> virus = new ArrayDeque<>();

    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];

        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.addLast(new Node(i, j)); // 바이러스 있는 노드
                }
            }
        }

        ArrayDeque<Node> block = new ArrayDeque<>();
        int answer = 0;

        for (int i = 0; i < N * M - 2; i++) {
            if (map[i / M][i % M] != 0) continue;
            block.addLast(new Node(i / M, i % M));

            for (int j = i + 1; j < N * M - 1; j++) {
                if (map[j / M][j % M] != 0) continue;
                block.addLast(new Node(j / M, j % M));

                for (int k = j + 1; k < N * M; k++) {
                    if (map[k / M][k % M] != 0) continue;
                    block.addLast(new Node(k / M, k % M));
                    BFS(block);
                    answer = Math.max(answer, BFS(block));
                    block.pollLast();
                }
                block.pollLast();
            }
            block.pollLast();
        }

        System.out.println(answer); // 정답
    }

    private static int BFS(ArrayDeque<Node> block) {
        // 새로 새울 벽을 매개변수로 받는다. 새로 새울 벽마다 BFS를 돌려야하기 때문

        int[][] map2 = new int[N][M];

        // 기존 맵은 복사해둔다.
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                map2[i][j] = map[i][j];
            }
        }

        // 벽 3개를 세운다.
        for (Node node : block) {
            map2[node.r][node.c] = 1;
        }
        ArrayDeque<Node> queue = new ArrayDeque<>();

        for (Node node : virus) {
            queue.addLast(node);
        }

        while (!queue.isEmpty()) {
            Node now = queue.pollFirst();

            for (int i = 0; i < 4; i++) { // 상하좌우 탐색
                int nr = now.r + rx[i];
                int nc = now.c + ry[i];

                // 예외 처리
                if (nr < 0 || nc < 0 || nr >= N || nc >= M)
                    continue; // 맵 밖으로 나가는 경우

                if (map2[nr][nc] == 1)
                    continue; //벽인 경우

                if (map2[nr][nc] == 0) {
                    map2[nr][nc] = 2; // 바이러스에 감염 시킴
                    queue.addLast(new Node(nr, nc));
                }
            }
        }

        int cnt = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (map2[i][j] == 0)
                    cnt++;
            }
        }

        return cnt;
    }
}

 

제대로 풀지 못해 풀이를 참고했다. 며칠 뒤에 다시 풀어봐야겠다...

 

 

 

---

📌 TIL

Arrays.deepToString()

안에 있는 데이터가 2차원 배열이더라도 쭉 다 출력해준다.