[백준 / BOJ] 9376 탈옥

문제

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

9376번: 탈옥

상근이는 감옥에서 죄수 두명을 탈옥시킬려고한다.

N*M크기의 감옥이있고, 감옥은

# : 문

. : 빈 공간

$ : 죄수

로 구성되어있으며, 죄수는 항상 2명이다

(문이 있는곳은 지나가기위해 문을 열어야한다.)

 

모든 죄수를 탈출시키기 위해서 열어야 하는 문의 최솟값을 출력하는 문제였다.

 

풀이

다익스트라로 풀은 문제다.

 

처음 문제를보고 그냥 BFS를 돌리면 될것같다고 생각했는데, 한 죄수가 밖으로 나가는 최소경로가 두 죄수모두에게 해당하지않으므로, 단순 탐색으로는 풀수없었다.

예를들어, 1번 죄수가 탈출하면서 임의의 문을 열어놓았다면, 2번죄수는 자신의 최소경로보다, 1번죄수가 열어놓은 길로 탈출하는게 이득이다. 

 

문제는 다익스트라를 2번 수행하며 풀었다.

 

로직은 다음과 같다.

 

죄수들이 임의의 지점 (y,x)에서부터 겹쳐서 이동한다 했을때, 겹쳐지는 (y,x)지점부터 밖으로 나가기까지 열어야하는 문의 최솟값을 찾는다.

즉, 모든 (y,x)에 대해서, 밖으로 나가기까지의 최소경로를 구한후, 각각 죄수의 출발지점부터 모든 (y,x)까지 도달하기위해 열어야하는 문의 갯수를 찾으면된다.

 

예제 1의 테케 1번의 경우 (지나갈수없는곳 벽 은 = 로 표현한다)

 

====1====

=2221222=

====1====

=3322233=

=========

와 같이 만들어준다.

 

이제, 죄수의 위치에서 밖으로 나가기위해 열어야하는 문의 갯수를 각각 구한다.

 

1번죄수(왼쪽아래)는 다음과 같이 업데이트 된다.

 

====3====

=3332333=

====2====

=0112233=

=========

 

2번 죄수(오른쪽 아래)는 다음과 같이 업데이트 된다.

 

====3====

=3332333=

====2====

=3322110=

=========

 

이제, 모든 칸을 순회하며, 최솟값을 업데이트 해준다.

 

이때, 

두 죄수가 나가기 위해 열어야하는 문은 다음과 같이 계산할수있다.

 

열어야하는 문의 수 = (1번죄수가 y,x지점까지 도달하기위해 열어야하는 문의 수) + (2번 죄수가 y,x지점까지 도달하기위해 열어야하는 문의 수) + (y,x에서 밖으로 나가기위해 열어야하는 문의 수)

이때, y,x지점에 문이 있다면, (1번죄수, 2번죄수, 첫번째로 수행한 경로업데이트)3가지에서 중복해서 문을 연다. 따라서, 열어야하는 문의수에 -2를 취한다.

 

위 과정을 구현하면된다.

 

한 가지 반례가 있었는데,

두 죄수가 만나지않고, 서로 다른 통로로 이동하는 경우이다.

 

1

3 7

***#***

#$###$#

*******

 

위 경우에 1번 죄수와 2번죄수는 각각 왼쪽, 오른쪽 문을 열고 나가는게 최소이며 이때, 답은 2이다.

 

따라서, 죄수가 나가기 위해 열어야하는 문의 수를 구하는 다익스트라를 수행할때, 각각죄수의 최솟값을 구해놓고, 더한값으로 열어야하는 문의수를 초기화 해놓아야한다.

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/9376%20%ED%83%88%EC%98%A5/main.cpp

devxb/JJUNalgo