고인물을 지양하는 블로그

문제는 다음과 같다 대충 위와 같이 주어진 성곽이 있다. 실선은 벽을, 점선은 벽이 없어 지나다닐 수 있는 공간을 의미한다. 이 때, 1. 이 성에 있는 방의 수 2. 가장 넓은 방의 넓이 3. 하나의 벽을 제거하여 얻을 수 있는 가장 큰 방의 크기 를 구하는 것이 문제이다. 1, 2번은 DFS/BFS를 여러 번 호출하면 되는 기본적인 그래프 탐색 문제이지만, 3번이 이 문제의 문제라 할 수 있겠다. 다른 분들의 3번 문제 해결 방법을 살펴보니 주로 실제 벽을 제거하고, BFS을 통해 벽을 하나 제거하여 얻을 수 있는 가장 큰 방의 크기를 구하는데, 2번 문제를 해결하기 위해 각 방들의 넓이는 이미 구해져 있을것이므로, 벽을 하나 하나 허물며 탐색하는것은 조금 낭비처럼 느껴졌다. 내 해결방법은 다음과 같..