백준 9376 탈옥

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

9376번: 탈옥

먼저 1명이 탈출한다고 생각해보자. BFS를 통해 Flood Fill을 돌리는데, 지나온 문의 개수가 0개일때, 1개일때, ... 순서대로 방문하면 된다.

구현은 각각의 위치를 방문할 때 인접한 위치가 비어 있으면 현재 사용중인 큐에 넣고, 문이면 다음 큐에 넣어서 BFS를 돌리는 방식으로 하였다. 각각의 위치에 몇번째 큐에서 방문하였는지를 기록하면 된다. 필자는 귀찮아서 큐 10000개로 처리하였지만, 큐2개로 잘 처리해도 해결할 수 있을 것이다.

감옥의 테두리에서 몇번째 큐에서 방문하였는지가 탈옥 과정에서 연 문의 수가 된다. 이것의 최소값을 찾으면 1명짜리 문제는 해결된다.

 

이제 2명이 탈출하는 경우를 따져야 하는데, 2가지 경우를 생각해야 한다. 

1. 두 명이 따로 탈출하는 경우

2. 두 명이 탈출하는 중에 만나는 게 가능한 경우

 

1은 두 사람에 대해 위의 내용을 처리하고 두 값을 합하면 된다. 

 

2는 임의의 지점을 잡아 그 지점에서 만나서 바깥으로 나간다고 생각하면 된다. 이 부분을 해결하기 위해서는 감옥의 테두리 지점들을 보면서 빈 공간이면 첫번째 큐에, 문이면 두번째 큐에 넣고 시작하는 BFS를 하나 더 돌려서 총 3번의 BFS를 돌렸다. 그리고 각 지점을 보면서 그 지점이 만나는 지점이라고 생각해 3개의 BFS에서 얻어진 값을 더하면 되는 것이다. 

마지막으로 이 지점이 문인지 아닌지에 대해 처리를 해주자. 문이면 3번 카운트되므로 2를 빼야된다.

 

1번째 TC에 대해 해당 풀이를 적용한 그림은 다음과 같다. 

1번째 죄수에 대한 BFS

바깥에서 보는 BFS

표시한 지점에서 세 BFS의 값을 합한 값이 6이고, 해당 지점이 문이므로  2를 빼면 4가 얻어진다. 이게 최소라 해당 TC의 답은 4가 된다.