[BOJ/DFS+BFS] 백준 14502 - 연구소 (Java)

14502 - 연구소

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

문제

바이러스 확산을 막기 위해 연구소 벽을 세우려 함
연구소 크기 NxM 직사각형, 직사각형은 1x1 정사각형으로 나눠져 있음
/ 빈 칸, 벽으로 이뤄져 있으며 벽은 칸 하나를 가득 차지
/ 일부 칸은 바이러스 존재, 상하좌우로 인접한 빈 칸 모두 퍼져나갈 수 있음
/ 세울 수 있는 벽의 개수 3개고 꼭 세워야 함
=> 연구소 지도가 주어졌을 때 얻을 수 있는 안전 영역의 크기의 최댓값

입력
첫째 줄: 지도의 세로 크기 N, 가로 크기 M (3 <= N, M <= 8)
둘째 줄 ~ N개의 줄: 지도 모양 (0 빈 칸, 1 벽, 2 바이러스)
(2 <= 2의 개수 <= 10, 3 <= 빈 칸 개수)
출력: 얻을 수 있는 안전 영역의 최대 크기

---

풀이

DFS(백트래킹)

벽 세우기 

• 벽 3개 세우면 바이러스 퍼트리기(`bfs()`) 
• 지도 순회하면서 빈 칸(0) => 벽 3개 세운 모든 조합 시도
  • `map[i][j] = 1`: 벽 세우기
  • `dfs(cnt + 1)`: 벽 하나 더 생겼으니 다음 벽 세우러 재귀 호출
  • `map[i][j] = 0`: 재귀 끝나면 벽 다시 지움 (원상 복구)

static void dfs(int cnt) {
    if (cnt == 3) {
        bfs();
        return;
    }

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

 

BFS

바이러스 퍼트리고 남은 빈 칸 계산해서 `maxSafe` 갱신

• `copy`: `map`은 DFS에서 벽 세우며 변함 -> 별도의 `copy`에서 시뮬레이션 => 원본 보존
• 초기 바이러스(2) 큐에 넣고 하나씩 꺼내면서 상하좌우 확산

static void bfs() {
    int[][] copy = new int[N][M];
    Queue<int[]> q = new LinkedList<>();

	// 지도 복사 + 바이러스 위치 저장
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            copy[i][j] = map[i][j];
            if (copy[i][j] == 2) q.offer(new int[]{i, j});
        }
    }
	
    // 바이러스 퍼뜨리기
    while (!q.isEmpty()) {
        int[] cur = q.poll();

        for (int d = 0; d < 4; d++) {
            int nx = cur[0] + dx[d];
            int ny = cur[1] + dy[d];

            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if (copy[nx][ny] == 0) {
                copy[nx][ny] = 2;
                q.offer(new int[]{nx, ny});
            }
        }
    }

	// 안전 구역 계산
    int safe = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (copy[i][j] == 0) safe++;
        }
    }

    maxSafe = Math.max(maxSafe, safe);
}

---

코드

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

// 연구소
public class boj_14502 {
    static int N, M;
    static int[][] map;
    static int maxSafe = 0;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};

    static void dfs(int cnt) {
        if (cnt == 3) {
            bfs();
            return;
        }

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

    static void bfs() {
        int[][] copy = new int[N][M];
        Queue<int[]> q = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                copy[i][j] = map[i][j];
                if (copy[i][j] == 2) q.offer(new int[]{i, j});
            }
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll();

            for (int d = 0; d < 4; d++) {
                int nx = cur[0] + dx[d];
                int ny = cur[1] + dy[d];

                if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if (copy[nx][ny] == 0) {
                    copy[nx][ny] = 2;
                    q.offer(new int[]{nx, ny});
                }
            }
        }

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

        maxSafe = Math.max(maxSafe, safe);
    }

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

        dfs(0);
        System.out.println(maxSafe);
    }
}