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

1. 문제설명

바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소 크기는 N x M인 직사각형으로 나타낼 수 있고, 연구소는 빈 칸과 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이다. (꼭 3개)

주어진 연구소 정보에서 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다.

벽 3개를 세운 뒤, 바이러스가 퍼질 수 없는 안전 영역 크기의 최대값을 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 512MB

 

2. 접근 방식

• 연구소에 3개의 벽을 세우는 모든 경우를 DFS를 통해 구한다. (백트래킹 사용)
• 3개의 벽을 세운 경우 바이러스를 퍼트리는 과정에 BFS를 사용하여, 안전 구역을 구한다.
  • 바이러스가 있는지 체크하는 `boolean[][] virus` 를 이용해, 바이러스 위치를 저장한다.
• BFS로 구한 안전 구역은 최대값인지 확인하고 갱신한다.

⇒ DFS로 벽을 3개 세운 경우를 구하고, BFS로 바이러스가 퍼진 경우를 구해, 안전 구역을 계산한다.

 

3. 다른 풀이

REF

[백준 14502] - 연구소 자바(JAVA)

문제의 접근 방식을 알게 해준 풀이이다.

BFS 메서드에서 위 레퍼런스와 조금 다르게 풀이한 부분이 있다.

 

1. 나의 풀이 => virus 배열을 사용한 방식

• 바이러스의 확산 여부를 체크했다.
• 원본 lab 배열과 함께 사용하여
  • while문에서는 큐에 추가할지 파악한다. (`if(lab[nx][ny]==0 && !virus[nx][ny])`)
  • 안전 구역을 계산할 때 안전 구역인지 파악한다. (`if(lab[i][j] == 0 && !virus[i][j])`)

 

2. 다른 사람의 풀이 => copyMap 배열을 사용한 방식

• 연구소의 전체 상태를 복사하여 사용한다.
• 바이러스 확산, 벽, 빈 공간을 모두 한 배열에서 표현할 수 있다.

 

2번 방법이 더 가독성이 좋을 것 같다.

1번 방법은 메모리 사용이 2번 보다 적다. (boolean vs int)

 

4. 최종 코드

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

public class Main {
    static int n, m; // 연구실의 세로, 카로 크기
    static int[][] lab; // 연구실 정보
    static boolean[][] virus; // 바이러스 체크
    static int maxSafeZone = 0; // 안전 영역 크기의 최댓값

    static int[] dx = {-1, 1, 0, 0}; // 좌우
    static int[] dy = {0, 0, -1, 1}; // 상하

    static void dfs(int count) { // 벽의 개수를 매개변수로
        if(count == 3) { // 벽이 3개인 경우
            bfs(); // bfs 호출
            return;
        }

        // 연구소의 모든 칸 탐색
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(lab[i][j] == 0) { // 빈 칸이면
                    lab[i][j] = 1; // 벽 세움
                    dfs(count+1); // 벽 1 증가시켜 재귀 호출
                    lab[i][j] = 0; // 벽 취소 (백트래킹)
                }
            }
        }
    }

    static void bfs() { // 바이러스 퍼트리고, 안전 구역 계산
        Queue<int[]> q = new ArrayDeque<>();
        virus = new boolean[n+1][m+1];

        // 현재 연구소 상태를 임시 배열에 복사
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                if(lab[i][j] == 2) {
                    q.add(new int[]{i, j});
                    virus[i][j] = true;
                }
            }
        }

        while (!q.isEmpty()) {
            int[] cur = q.poll(); // 큐에서 현재 위치 꺼냄
            for(int i=0; i<4; i++) { // 상하좌우 탐색
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];
                // 다음 위치가 이동 범위에 속하고, 빈 칸일 경우
                if(nx>0 && nx<=n && ny>0 && ny<=m &&
                        lab[nx][ny]==0 && !virus[nx][ny]) {
                    virus[nx][ny] = true; // 바이러스 확산
                    q.add(new int[]{nx, ny}); // 큐에 다음 위치 추가
                }
            }
        }

        int count = 0; // 안전 구역 개수 저장
        // 안전 구역 계산
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
		            // 연구소에서 빈 칸이고, 바이러스에 감염되지 않았으면
                if(lab[i][j] == 0 && !virus[i][j])
                    count++; // 안전 구역 증가
            }
        }
        maxSafeZone = Math.max(maxSafeZone, count); // 최댓값 갱신
    }

    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());
        lab = new int[n+1][m+1];
        for(int i=1; i<=n; i++) {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=m; j++) {
                lab[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

 

5. 느낀점 or 기억할정보

지금까지 풀어본 DFS/BFS 문제는 모두 둘 중 하나만 사용해서 한 번에 구하는 풀이였는데, 이 문제도 처음에 그런 식으로 해결하려 했더니 적절한 방법이 생각나지 않았다. 

이 문제는 DFS와 BFS 모두 사용해야 풀 수 있는 문제였다. DFS/BFS 의 응용 버전 같았다.

이렇게 DFS 호출 다음에 조건을 충족했을 시 BFS를 호출하는 방법을 알게 되어서 좋았다. 다음에도 이런 문제를 풀게 되면 방법을 바로 떠올렸으면 좋겠다.