백준 14502번 : 연구소 풀이 (Java)

www.acmicpc.net/problem/14502

14502번: 연구소

생각을 너무 오래했다.

Key Point

벽 부수고 이동하기(simju9397.tistory.com/11) 문제를 풀고 나서 보고 나니 오히려 혼동이 생겨 고민을 굉장히 오래 했다. 이 문제의 핵심은 그냥..

1. 빈 공간들과 바이러스들을 각각의 ArrayList에 담는다.

2. 빈 공간들 중에서 벽으로 만들 3개의 공간을 선택한다. 그렇다. 조합과 완전탐색 문제이다.

3. 조합을 만들었다면, 첫 바이러스들의 위치를 담은 ArrayList를 기반으로 Queue 를 만든 뒤에, BFS를 돌려준다.

4. 탐색 하면서 감염되는 공간들은 0에서 2로 바꿔준다.

5. 탐색이 끝난 후, 여전히 0인 '안전 공간'들의 갯수를 세어 정답에 담아 놓은 값과 비교해 큰 값을 정답으로 담는다.

 

3 <= N,M <= 8 이라는, 굉장히 작은 범위이기 때문에 이렇게 풀어도 풀린다. 나는 이전 문제와 비교해 겁을 먹고, 3개니까 3차원 배열을 visited[N][M][4]; 이런 식으로 만들어줘야 하나 싶어서 한시간 넘게 날렸다.

 

앞으로는 input의 범위를 보고, 작은 것은 무조건 완전 탐색부터 생각하는 습관을 들여야겠다. 완전 탐색은 모든 알고리즘의 기본이고 제일 쉬우니까 말이다.

 

Source Code

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

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static int N,M, ans = Integer.MIN_VALUE;
    static int[][] map;
    static ArrayList<Node> viruses; // 초기 바이러스의 위치
    static ArrayList<Node> safes; // 안전 장소들의 위치
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    static void input() throws IOException {
        StringTokenizer nm = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(nm.nextToken());
        M = Integer.parseInt(nm.nextToken());
        map = new int[N][M];
        viruses = new ArrayList<>();
        safes = new ArrayList<>();
        for(int i = 0 ; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            for(int j = 0;j < M; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                if(map[i][j] == 2) {
                    viruses.add(new Node(i, j)); // 각각
                } else if(map[i][j] == 0) {
                    safes.add(new Node(i, j)); // 담아준다
                }
            }
        }
    }

    private static void makeCombination(int cnt, int start ,int[] arr) {
        if(cnt == 3) {
            int[][] newMap = new int[N][M];
            for(int i = 0 ; i < N; i++) {
                newMap[i] = map[i].clone(); 
                // 이거 중요한 부분인데, 2차원 배열을 복사하는 것이기 때문에
                // 반복문을 돌면서 한 열씩 복사해줘야 한다!!!
            }
            for(int i = 0; i < 3; i++) {
                Node n = safes.get(arr[i]); // 뽑은 인덱스들을 반복문을 돌면서 Node 를 가져온 뒤
                newMap[n.x][n.y] = 1; // 뽑힌 노드들을 벽으로 만들어서
            }
            bfs(new boolean[N][M], newMap); // bfs 에 던져준다.
            return;
        }
        for(int i = start; i < safes.size() ; i++) {
            arr[cnt] = i; // 0~safes.size()-1 의 범위에서 인덱스 3개를 조합으로 뽑는다.
            makeCombination(cnt+1, i+1, arr);
        }
    }


    static void bfs(boolean[][] visited, int[][] map) {
        Queue<Node> queue = new LinkedList<>(viruses); // 초기 바이러스의 위치들을 담아준다.
        // 한 번에 담아야 여러 바이러스 들이 같이 확산을 시작할 것이다.
        while (!queue.isEmpty()) {
            Node start = queue.poll();
            int sx = start.x;
            int sy = start.y;
            visited[sx][sy] = true;
            for(int i = 0 ; i < 4; i++) {
                int nx = sx + dx[i];
                int ny = sy + dy[i];
                if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                if(visited[nx][ny] || map[nx][ny] != 0) continue;
                // 방문했거나, 0이 아닌 경우는 넘겨준다(이미 확산됐거나(2), 벽이거나(1) )
                visited[nx][ny] =true;
                queue.add(new Node(nx, ny));
                map[nx][ny] = 2; // 방문한 지점은 확산된 것이므로 2로 바꿔준다.
            }
        }
        int count = 0;
        for(int i = 0 ; i < N; i++) {
            for(int j = 0 ; j < M; j++) {
                if(map[i][j] == 0) { // 이후 2차원 배열을 돌면서 안전 지점의 갯수를 세준다.
                    count++;
                }
            }
        }
        ans = Math.max(ans, count);
    }

    static void solve() {
        makeCombination(0,0,new int[3]);
        System.out.println(ans);
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedReader.close();
    }
}