BOJ 14502. 연구소

BOJ 14502 연구소는 브루트포스와 BFS를 함께 쓰는 전형적인 문제다. 핵심은 벽을 세우는 모든 경우를 탐색한 뒤, 각 경우마다 바이러스 확산 결과를 시뮬레이션하는 것이다.

문제의 핵심 구조

• 빈 칸 중 3곳을 골라 벽을 세운다
• 바이러스가 상하좌우로 퍼진다
• 확산이 끝난 뒤 안전 영역의 크기를 계산한다
• 가능한 모든 벽 배치 중 최대 안전 영역을 찾는다

즉, 선택과 시뮬레이션이 결합된 문제다.

왜 브루트포스가 가능한가

빈 칸의 수가 아주 크지 않기 때문에, 3개의 벽을 세우는 조합을 모두 시도해도 감당 가능하다. 이 문제는 최적화 트릭보다 모든 경우를 빠짐없이 생성하는 구조를 만드는 것이 우선이다.

바이러스 확산은 어떻게 푸는가

바이러스 위치를 시작점으로 잡고 BFS를 돌리면 된다.

• 초기 바이러스 좌표를 큐에 넣는다
• 상하좌우 빈 칸으로 퍼뜨린다
• 방문 또는 감염 처리를 한다

여기서 중요한 것은 원본 맵을 그대로 쓰지 않고, 벽 배치가 반영된 복사본에서 시뮬레이션해야 한다는 점이다.

구현에서 자주 틀리는 부분

원본 맵을 직접 수정하는 경우

조합을 하나 시험할 때마다 맵이 오염되면 다음 경우의 수 계산이 틀어진다. 그래서 매 시도마다 복사본을 쓰는 편이 안전하다.

벽 조합 생성과 BFS 책임을 섞는 경우

벽 조합을 만드는 로직과 바이러스 확산 로직이 섞이면 디버깅이 어려워진다. 보통은:

• 조합 생성
• 맵 복사
• BFS 확산
• 안전 영역 계산

순으로 역할을 분리하는 편이 좋다.

풀이 전략 요약

1. 빈 칸 좌표를 모은다
2. 3개를 고르는 조합을 만든다
3. 각 조합마다 맵을 복사하고 벽을 세운다
4. 바이러스 좌표들로 BFS를 수행한다
5. 남은 안전 영역 수를 계산한다
6. 최댓값을 갱신한다

정리

이 문제는 “BFS 문제”이기도 하지만, 더 정확히는 조합 + 시뮬레이션 문제다. 어떤 알고리즘을 붙일지보다, 경우의 수 생성과 확산 시뮬레이션을 안정적으로 분리하는 것이 풀이의 핵심이다.