[BOJ] 14502 연구소 - JAVA

1. 문제

14502번: 연구소

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 

일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.

---

2. 풀이

입력 및 출력(메인)

int[][] map	입력정보 저장 배열. bfs탐색을 하면서도 사용한다.
N, M	입력 크기 N 세로 M 가로
MIN	새로 퍼질 바이러스 양의 최솟값(결과에 사용)
ArrayList<int[]> list	0의 위치 저장
ArrayList<int[]> virus	바이러스 위치 저장. queue의 초기값으로 활용
Queue<int[]> queue	bfs탐색에서 활용

1.  입력값이 0이라면(빈 공간) list에 추가하고, 2(바이러스)라면 virus에 추가한다.

2.  벽 뽑는 조합 함수를 부른다. 이 함수는 벽 세개를 뽑으면 그 상태에서 새로 퍼질 바이러스 양을 구한다.

3.  처음에 입력받은 0의 개수-추가로 세운 벽 3개-새로 퍼진 바이러스 수(MIN)을 출력한다.

static int[][] map;
static int N, M, MIN = Integer.MAX_VALUE;
static ArrayList<int[]> list, virus;
static int[][] deltas = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
static Queue<int[]> queue = new ArrayDeque<>();

public static void main(String[] args) throws Exception {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st = new StringTokenizer(in.readLine());
   N = Integer.parseInt(st.nextToken());
   M = Integer.parseInt(st.nextToken());
   map = new int[N][M];
   list = new ArrayList<>();
   virus = new ArrayList<>();

   for (int i = 0; i < N; i++) {
      st = new StringTokenizer(in.readLine());
      for (int j = 0; j < M; j++) {
         map[i][j] = Integer.parseInt(st.nextToken());
         if (map[i][j] == 0) list.add(new int[]{i, j});
         else if(map[i][j]==2) virus.add(new int[]{i,j});
      }
   }

   pick(0, 0);

   System.out.println(list.size()-3-MIN);

}

 

벽 뽑는 함수

1.  list.size()개에서 3개를 뽑는다. 

2.  i번째 0을 뽑으면 그 자리를 map에 아무 숫자로 채워넣고(디버깅을 쉽게 하기 위해 5로 설정했다.) 다음 0을 뽑으러 간다. 전부 뽑고 돌아왔다면 같은 자리를 다시 0으로 만든다.

3.  0을 세번 뽑았으면 count()함수를 불러서 현 상황에서 새로 퍼질 바이러스의 양을 알아낸다.

4.  3번 값과 지금까지 저장된 MIN을 비교해서 더 작은 값을 저장한다. 

private static void pick(int start, int cnt) {
   if (cnt == 3) {
      MIN = Math.min(MIN,count());
      return;
   }

   for (int i = start + 1; i <= list.size(); i++) {
      int[] pos = list.get(i - 1);
      map[pos[0]][pos[1]] = 5;
      pick(i, cnt + 1);
      map[pos[0]][pos[1]] = 0;
   }
}

 

바이러스가 새로 얼마나 퍼지는지 반환하는 함수

1.  map을 바꾸면서 움직이기 때문에 원본 복사가 필요하다. 새 next배열을 만들어서 map을 deepcopy한다.

2.  초기 virus가 저장된 리스트를 돌면서 bfs탐색에 쓸 큐에 추가한다.

3.  큐가 빌 때까지 다음 위치를 찾아 큐에 넣고, 뽑기를 반복한다.

4.  큐에 넣을 수 있는 값은 map[nr][nc]가 0인 값이다. 큐에 넣으면서 그 자리를 -1로 채운다.(방문처리)

5.  4번과 동시에 count를 하나 더한다. 뽑으면서 +1하지 않고(=9번째 줄에서 count++하지 않고) 다음 수를 찾으면서 더하는 이유는 원래 있던 바이러스는 카운팅하지 않도록 하기 위해서다.

private static int count() {
   int[][] next = deepCopy(map);
   for(int[] v:virus) queue.offer(v);

   int[] pos;
   int count = 0;
   while (!queue.isEmpty()) {
      pos = queue.poll();

      for (int d = 0; d < 4; d++) {
         int nr = pos[0] + deltas[d][0];
         int nc = pos[1] + deltas[d][1];
         if (nr < 0 || nr >= N || nc < 0 || nc >= M || map[nr][nc] != 0) continue;
         map[nr][nc] = -1;
         queue.offer(new int[]{nr,nc});
         count++;
      }
   }

   map = deepCopy(next);
   return count;
}

 

깊은 복사하는 함수

얕은 복사는 값이 동시에 바뀌기 때문에 깊은 복사가 필요하다. Object.clone()은 얕은 복사를 하지만 primitive type배열은 clone을 사용해도 깊은 복사가 된다. 

private static int[][] deepCopy(int[][] origin){
   int[][] next = new int[N][M];
   for(int i=0;i< N;i++){
      next[i] = origin[i].clone();
   }
   return next;
}

---

3. 결과