[C++] 백준 14502 - 연구소

🔐 백준 14502 - 연구소

https://www.acmicpc.net/problem/14502

🔑 풀이

이 문제는 DFS, BFS를 적절히 활용하여 해결할 수 있는 전형적인 백트래킹 문제이며,

다음과 같은 과정으로 문제를 풀 수 있다.

• 벽 3개 세우기

  • 빈 칸 중 3개를 선택하여 벽을 세운다. DFS를 사용하여 구현한다.

• 바이러스 퍼뜨리기

  • BFS를 사용하여 바이러스가 연구소 전체로 퍼지는 과정을 시뮬레이션한다.

• 안전 영역 계산

  • 바이러스가 모두 퍼진 후 남아 있는 빈 칸의 개수를 계산한다.

• 최대값 갱신

  • 모든 경우를 탐색하여 안전 영역의 최대 크기를 갱신한다.

🧩 코드