[BOJ][14502번] 연구소

안녕하세요 Dibrary입니다.

이번에는 제가 BFS/DFS에 아주 약간? 자신감이 생겨서 도전했다가 몇 시간을 .. 날려버린 문제를 정리해보겠습니다.

알고보니 BFS/DFS같은 그래프 풀이방법 만 쓰는 게 아니라, 여기에 모든 경우의 수 까지 같이 확인해야 하는 문제였어서 처음 접한 저는 매우 어려웠었습니다.

14502번: 연구소

 

---

처음에 문제를 보고 곧바로 "BFS를 쓰믄 되겠다! " 라는 생각이 제일 먼저 떠올랐습니다.

왜냐하면, 문제에서 "바이러스는 퍼져나갈 수 있다" 라고 나왔기 때문이죠.

 

근데 생각을 하다가 잠시 멈칫 하게 된 부분은 '3개의 벽을 세울 수 있다' 이 부분입니다.

3개는 아무렇게나 세울 수 있는데, 마침 그 위치가 바이러스가 확산 된 이후에 남는 공간이 '최대'가 되게 세워야 한다는 것이죠.

 

우선 BFS를 통해 바이러스가 확산되는 코드는 금새 작성할 수 있었습니다.

 

근데 1을 세울 때 여러 생각이 들더라구요.

1. 1을 세우는 위치가 마침 2가 더 확산 안되게 막는 '그 위치'인지 어떻게 알 수 있을까
2. 마침 '그 위치'인데 상,하,좌,우,대각 다 고려해서 딱 그 위치를 막아야 하는지를 어떻게 알 수 있을까
3. 1을 1개만 쓰지 않고 막는 경우는 어떤 것을 또 고려해야 할까

아주 생각이 끝이 없었습니다.

 

---

막상 답은 간단했습니다.

1을 3개만 세울 수 있고, 전체 지도는 최대 8*8까지만 주어지므로 모든 경우의 수를 다 따져도 되는 것이죠. (막대만 세우는 것을 고려해보면 62*62*62 = 238328 밖에 안 됩니다. 약 1억번의 연산이 1초라고 가정할 때 1초보다 짧은 것이죠)

그래서 그냥 막대를 모든 경우에 다 세워보면서 해당 경우마다 '바이러스 확산'을 시킨 뒤, 0의 갯수를 세면 되는 겁니다.

당연히 0의 갯수를 센 것 중에 최대 갯수를 세면 되는 것이죠.

바로 이게 진짜 문제였습니다.

막대를 어디에 세우느냐가 중요한게 아니라 '최대 갯수'만 알면 되는 것입니다. 막대가 어디에 세우는지는 관심없다 이거죠

 

그래서 BFS에 모든 경우의 수를 고려하는 코드는 아래와 같습니다.

먼저 입력을 받고, 0인 경우의 위치와 2의 위치를 미리 별도로 담아둡니다.

0은 막대를 세울 수 있는 위치로 쓰이고, 2는 바이러스 확산을 위한 시작점으로 쓰이는 것이죠.

 

그리고 바이러스 확산을 시키고 0의 갯수를 구하는 bfs함수를 정의합니다.

 

마지막으로, 벽을 세워야겠죠? for문을 3번 돌면서 모든 경우의 수(0으로 처음에 담아놓은 위치 갯수)에 대해 벽을 세우고 지우고 하면서 최대 갯수를 구합니다.

 

2가지 이상의 개념을 섞어서 활용해야 하는 문제는 처음 겪어봐서 정말 어려웠는데, 다음부터는 이런 어려움은 쉽게 극복할 수 있을거 같네요.