[9328] 열쇠

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

9328번: 열쇠

오답 판정으로 고생했던 문제. 다른 분의 풀이를 보니 접근 불가능한 문을 마주했을 때와 이후 열쇠를 얻어 방문할 수 있게 되는 부분에서의 처리방법이 달랐다. 

 

풀이

bfs를 수행할 때 크게 4가지 조건을 확인하면서 경로를 탐색해야 한다.

• 빈 공간을 마주한 경우
• 문서를 마주한 경우
• 문을 마주한 경우
• 열쇠를 마주한 경우

문서와 빈 공간의 경우 알맞게 처리하고 경로탐색을 수행하면 된다.

헤맸던 부분은 열쇠를 마주했던 부분이다. 문과 열쇠 각각 두 가지 경우로 다시 나뉜다.

• 열 수 있는 문을 마주한 경우 -> 그대로 경로 탐색 수행
• 열 수 없는 문을 마주한 경우 -> 해당 좌표를 담아두고 다음 경로 탐색
• 이미 얻었던 열쇠를 마주한 경우 -> 그대로 경로 탐색 수행
• 기존에 없던 열쇠를 마주한 경우 -> 기존에 마주했던 열 수 없었던 문들 중 해당 열쇠로 열 수 있는 문 좌표에 대해 경로 탐색 수행

기존의 코드는 맵을 입력받을 때 모든 문의 좌표를 담아두고 경로탐색 시 새로운 열쇠를 얻을 때마다 좌표를 담아두었던 배열을 돌며 탐색을 수행했었다. 문제는 그렇게 되면 벽으로 둘러싸여 도달할 수 없는 문의 경우를 매번 마주해야 하고, 이러한 예외처리를 해주어야 하는데, 거기서 부터 해결을 못해 오답 판정을 받았다.

 

그리고 또 한번 곤욕을 겪은 부분이 경로 탐색 시작 지점에 대한 부분이다. 처음엔 문제에서 주어진 대로 맵의 테두리만 돌면서 탐색 가능한 지점을 직접 찾는 코드를 적었다. 여기서부터 시작 가능한 지점에 대해서 다시 한번 위의 4가지 경우에 맞게 예외처리를 해주어야 했고 이렇게 되면서 코드 양도 많아지고 오답 판정을 받았을 때 찾아봐야 할 지점이 너무 많아서 해결을 못했다.

 

다른 분의 풀이에서 이 부분도 잘 해결한 모습을 찾을 수 있다. 입력받은 맵 주변에 빈 공간으로 한번 둘러주어 map[0][0]에서 경로를 탐색하게 되면 자연스럽게 4가지 조건에 대한 처리가 이루어지게 된다.

//입력된 지도				
*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*
.	.	.	.	.	.	.	.	.	.	.	.	.	*	*	$	*
*	B	*	A	*	P	*	C	*	*	X	*	Y	*	.	X	.
*	y	*	x	*	a	*	p	*	*	$	*	$	*	*	$	* 
*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*
						
//테두리 추가
.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.
.	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	.
.	.	.	.	.	.	.	.	.	.	.	.	.	.	*	*	$	*	.
.	*	B	*	A	*	P	*	C	*	*	X	*	Y	*	.	X	.	.
.	*	y	*	x	*	a	*	p	*	*	$	*	$	*	*	$	*	.
.	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	*	.
.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.	.

 

정답 코드