백준 14502 연구소

왜 상반기 기출문제를 풀 때 안풀어 보았는지는 모르겠지만, 기출 문제를 다시 한 번 풀어보는 과정에서 풀게 되었다.

 

안전한 곳의 수를 세면 되기 때문에, map을 입력 받을 때 그 수를 세어주었다. (2차원 배열을 다 돌면서 세지 않고 이렇게 하는 방법을 다른 문제에서 다뤄본 적이 있었다.)

 

일단 바이러스는 퍼져나가는 것이기 때문에 BFS로 풀어야 했고, 벽의 위치는 안전한 곳에서 3개를 고르는 조합이었기 때문에 DFS를 통해서 해결했다.

 

다만, DFS(재귀)를 돌면서 BFS를 돌아야 했기 때문에 시간 복잡도를 계산해보아야 했고, 충분하다는 생각이 들었다.(시뮬레이션 하는 것 말고는 다른 방법이 생각나지 않았다.)

 

Queue를 만들어 바이러스의 위치를 넣어주고, visit를 통해서 BFS를 돌렸다.

다만 BFS를 돌 때마다 인자로 전달하는 Queue와 visit 배열이 변경되기 때문에 BFS에 전달하기 전에 Queue와 visit를 복사한 후 전달해주어야 뒤 연산에 영향을 주지 않는다.

 

DFS에서 종료 조건과 답을 구해야 하는 조건문의 순서는 정말 중요하다. 이번에도 이 순서가 바껴서 2번이나 실패를 한 후에 테스트 케이스를 여러 개 만들어서 돌려보다가 찾게 되었다.

또한 답이 너무 늦게 나와서 왜 그런가 했는데, 답을 구하는 조건문에서 return을 해주지 않아서 였다.

2가지 모두 항상 하는 실수 인데 꼭 다시 실수하게 되는 것 같다. 

DFS에 아직 약한 것 같다. 재귀로 문제를 풀 때 좀 더 신중하게 풀어야 겠다.

 

아래는 코드이다.

BFS를 돌 때 안전 영역의 수가 이미 ans에 저장되어 있는 값보다 더 작아지면 더이상 BFS를 돌지 않고 return하면 좀 더 최적화를 시킬 수 있을 것 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static int ans, n, m, size;
    static int[] dr = { -1, 0, 1, 0 };
    static int[] dc = { 0, 1, 0, -1 };
    static int[] rows;
    static int[] cols;
 
    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());
 
        int[][] arr = new int[n][m];// 연구소
        int safe = 0;// 안전한 곳
 
        Queue<Integer> virus = new LinkedList<Integer>();
 
        int[][] visit = new int[n][m];// 방문지 체크
        rows = new int[64];// 안전한 곳 좌표
        cols = new int[64];
 
        ans = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                if (arr[i][j] == 0) {// 안전한 곳 저장
                    rows[safe] = i;
                    cols[safe++] = j;
                }
                if (arr[i][j] == 2) {// 바이러스 있는 곳 큐에 저장
                    virus.offer(i);
                    virus.offer(j);
                    visit[i][j] = 2;
                }
                if (arr[i][j] == 1)// 벽있는 곳 visit
                    visit[i][j] = 1;
            }
        }
        size = safe;
        perm(visit, virus, safe, 0, 0);
        System.out.println(ans);
    }
 
    static void perm(int[][] visit, Queue<Integer> virus, int safe, int cnt, int idx) {
        if (cnt == 3) {
            Queue<Integer> cpVirus = new LinkedList<>();
            for (int i = 0; i < virus.size(); i++)
                cpVirus.addAll(virus);
            int[][] cpVisit = new int[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    cpVisit[i][j] = visit[i][j];
                }
            }
            bfs(cpVirus, cpVisit, safe);
            return;
        }
        if (size <= idx)
            return;
 
        int row = rows[idx];
        int col = cols[idx];
        visit[row][col] = 1;
        perm(visit, virus, safe - 1, cnt + 1, idx + 1);
        visit[row][col] = 0;
        perm(visit, virus, safe, cnt, idx + 1);
    }
 
    private static void bfs(Queue<Integer> cpVirus, int[][] cpVisit, int safe) {
        while (!cpVirus.isEmpty()) {
            int row = cpVirus.poll();
            int col = cpVirus.poll();
 
            for (int i = 0; i < 4; i++) {
                int nr = row + dr[i];
                int nc = col + dc[i];
 
                if (nr < 0 || nr >= n || nc < 0 || nc >= m || cpVisit[nr][nc] != 0)
                    continue;
                cpVisit[nr][nc] = 2;
                cpVirus.offer(nr);
                cpVirus.offer(nc);
                safe--;
            }
        }
        ans = (ans < safe) ? safe : ans;
    }
}