[백준][14502번] 연구소

문제 URL

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

전체 풀이

유형은 완전탐색 + dfs를 이용해서 풀수있다.

큰 흐름은 다음과 같다.

1. 벽을 3개 세운다.
   • 백트래킹을 이용해서 벽을 3개 세울 수 있다. (값이 0인 곳. 즉, 아무것도 없는 곳에만 설치)
   • n*m개 중에서 3개를 뽑는 조합 알고리즘을 구현
   • 0 ~ n*m 까지 증가할떄 (i/m, i%m)을 좌표로 하면 2차원 배열의 인덱스를 구할수있다.
2. 바이러스를 퍼뜨린다.
   • 바이러스 퍼지는 것은 dfs를 이용할 수 있다.
3. 안전영역 개수를 구한다

package backjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static int n, m;
    public static int[] dx = {0, 0, 1, -1};
    public static int[] dy = {1, -1, 0, 0};
    public static int[][] map;
    public static int[][] tmpMap;
    public static boolean[][] visit;
    public static int max = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] str = br.readLine().split(" ");
        n = Integer.parseInt(str[0]);
        m = Integer.parseInt(str[1]);
        map = new int[n][m];
        tmpMap = new int[n][m];
        visit = new boolean[n][m];

        for (int i = 0; i < n; i++) {
            str = br.readLine().split(" ");
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(str[j]);
            }
        }

        buildWall(0, 0);
        System.out.println(max);
    }

//지도에 벽을 3개 만든다.
    public static void buildWall(int start, int idx) {
        if (idx == 3) {
            spreadVirus();
            return;
        }

//벽 순서조합
        for (int i = start; i < m * n; i++) {
            int x = i % m;
            int y = i / m;
            if (map[y][x] == 0) {
                map[y][x] = 1;
                buildWall(i + 1, idx + 1);
                map[y][x] = 0;
            }
        }
    }

//브루트포스로 여러 벽을 세웠을경우도 탐색해야 하므로 지도를 복사해야한다.
    public static void copyMap() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                visit[i][j] = false;
                tmpMap[i][j] = map[i][j];
            }
        }
    }

//바이러스 퍼뜨리기
    public static void spreadVirus() {
        copyMap();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visit[i][j] && tmpMap[i][j] == 2) {
                    dfs(j, i);
                }
            }
        }

        getSafeArea();
    }

    public static void dfs(int x, int y) {
        tmpMap[y][x] = 2;
        visit[y][x] = true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (0 <= nx && nx < m && 0 <= ny && ny < n && !visit[ny][nx] && tmpMap[ny][nx] == 0) {
                dfs(nx, ny);
            }
        }
    }

//안전 영역 크기 구하기
    public static void getSafeArea() {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (tmpMap[i][j] == 0)
                    cnt++;
            }
        }

        if (max < cnt) {
            max = cnt;
        }
    }
}