[백준] 14502번 - 연구소 (Java)(△)

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

14502번: 연구소

 

<문제 분석>

1. 바이러스가 퍼지는 걸 막으려면 벽을 세워야 하는데 벽의 개수는 3개이다.

2. 바이러스가 상하좌우로 번질 수 있다고 하니 BFS에서 큐에 넣은 것은 바이러스의 위치이다.

  2-1. BFS 호출 전에 for문을 돌려서 바이러스(2)를 다 큐에 넣자.

3. 이 문제는 탐색을 2번을 해야 한다. (벽 3개를 세우는 경우의 수, 바이러스 확산의 경우의 수)

  3-1. 벽 3개를 완전탐색(DFS)해서 하나씩 세우다가 3개가 되면 바이러스 탐색(BFS)을 시작한다.

    - 벽의 수가 DFS의 파라미터 depth가 된다. +1씩 증가해서 재귀호출 한다.

  3-2. 바이러스 탐색을 할 때 원본맵을 손상하면 안되기 때문에 복사맵을 사용한다.

    - 벽을 다시 세워야 하기 때문이다.

    - 바이러스 확산 시 0이면 2로 업데이트 하기 때문에 방문배열을 필요없다.

  3-3. 바이러스 탐색이 끝나면 매번 안전구역 값을 계산해서 max값을 업데이트 한다.

 

 

<코드 구현>

import java.util.*;

/*
[백준] 14502번 - 연구소 (Java)
*/

public class Main {
    int N, M;
    int map[][];

    class Point {
        int x;
        int y;
        Point (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    void InputData() {
        Scanner in = new Scanner(System.in);
        N = in.nextInt();
        M = in.nextInt();
        map = new int[N][M];
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                map[i][j] = in.nextInt();
            }
        }
    }

    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};
    int max = Integer.MIN_VALUE;
    void BFS() {
        Queue<Point> q = new LinkedList<Point>();
        int copied_map[][] = new int[N][M];
        
        // 바이러스 확산을 위해 벽을 세운 map을 복사한다.
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                copied_map[i][j] = map[i][j];
            }
        }

        // 복사된 맵에서 바이러스를 찾아서 큐에 넣는다.
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (copied_map[i][j] == 2) {
                    q.offer(new Point(i, j));
                }
            }
        }

        // 바이러스 확산 탐색 시작
        while (!q.isEmpty()) {
            Point tmp = q.poll();
            for (int i=0; i<4; i++) {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
                if (copied_map[nx][ny] != 0) continue;
                copied_map[nx][ny] = 2;
                q.offer(new Point(nx, ny));
            }
        }

        // 안전구역 계산
        int count = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (copied_map[i][j] == 0)
                    count++;
            }
        }
        max = Math.max(max, count);
    }


    void DFS(int wall_count) {
        // 종료조건은 벽이 3개
        if (wall_count == 3) {
            BFS();
            return;
        }
        // map[][]가 0이면 벽을 놓을 수가 있다.
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (map[i][j] == 0) {
                    map[i][j] = 1;// 빈자리에 벽을 세운다.
                    DFS(wall_count+1);// 다른 벽을 세우기 위해 재귀호출
                    map[i][j] = 0;// 다음 탐색을 위해 재귀에서 돌아왔을 때 벽을 다시 치운다.(!)
                }
            }
        }
    }

    void Solve() {
        //1. map에 벽 3개를 놓은 경우의 수 탐색
        //2. 벽이 3개가 되면 바이러스 확산되는 경우의 수 탐색
        //3. 바이러스 확산이 완료되면 안전구역 수를 카운트 해서 max값 업데이트
        DFS(0);
        System.out.println(max);
        
    }
    
	public static void main(String[] args) {
		Main m = new Main();
        m.InputData();
        m.Solve();
	}
}

 

<제출 결과>

 

<후기>

1. 탐색을 2개가 같이 있는 문제는 처음이라 DFS와 BFS를 동시에 사용한다고 생각을 못했다.

2. DFS의 조건이 만족하면 BFS를 호출하는 식의 구현을 요구하는 문제가 있음을 기억하자.

3. visited 배열을 사용하지 않고, map을 복사해서 계산하는 방식도 가능함.