BOJ 4001 - 미노타우르스 미궁

꽤 오래 전부터 보던 문제인데, 도저히 모르겠어 태그를 까고 생각해보았다. 

 

문제 요약

 

길 또는 장애물로 이루어진 격자가 주어진다. 이 때 장애물이나 시작, 끝 지점을 포함하지 않으면서 시작점에서 끝점으로 가는 경로를 차단하도록 설치할 수 있는 가장 작은 정사각형 장애물의 크기와 위치를 구하시오.

 

풀이

가는 경로가 벽으로 생각했을 때 잇는 경로로 바뀐다는 duality는 최근 여러 문제에서 등장한 바 있다. ICPC Sinchon Camp Contest에도 나왔고, 최근에는 코포에서도 한번 본 것 같다. 따라서, 이 문제에서도 같은 방법으로 접근해보자.

뭔가 '가장 작은' 정사각형의 크기를 구하는 것이므로 이분 탐색을 쓰고 싶지만, 그럴 수 없다. 조금만 생각해보면, 조건을 만족하는 장애물의 크기는 연속적이지 않을 수 있다. 

 

까지 생각한 후 막혀서 태그를 깠다. 버젓이 이분 탐색이 있으므로 단조성이 적용될 수 있는 부분을 찾아내보자.

 

1) 길을 막는가 여부와는 별개로, 설치할 수 있는 장애물의 크기는 단조적이다.

2) 설치할 수 있는가와 별개로, 길을 막는 장애물의 크기는 단조적이다.

 

1)의 경우에는 설치 가능->설치 불가로 바뀌고, 2)의 경우에는 막지 못함->막음으로 바뀐다.

1)은 장애물에 대한 누적합으로, 2)는 (왼쪽 아래 벽) 또는 (오른쪽 위 벽) 과 연결된 장애물에 대한 누적합으로 판별해줄 수 있다.

 

이제 2)로 이분 탐색을 한 후 가장 작은 장애물의 크기를 기준으로 설치할 수 있는 장애물이 있는지 판별하려다.. 뭔가 놓친 부분이 있었다.

 

이분 탐색의 질문을 "이 크기로 길을 막을 수 있는 위치가 하나라도 존재하나?"와 "이 크기로 장애물을 설치할 수 있는 위치가 하나라도 존재하나?"와 같이 하는 접근은 옳아 보이지만, 그렇지 않다.

이 경우 두 질문이 모두 참이더라도 두 위치가 같은지가 보장되지 않기 때문이다. 따라서 이 질문을 각 점에 대해 해 주어야 한다.

 

각 점에 대해 이분 탐색을 한 후, 2)->1) 또는 1)->2)의 순서로 가능한지 체크하며 정답을 갱신해주면 된다.

그래프 탐색 시 구현적으로 유의할 점이 조금 있으니 이만 조심하면 된다. 

 

클래스 문제답게 풀이가 참 멋지다.