[BOJ 25208] 백준 25208번 - 새벽의 탐정 게임

		2022 인하대학교 프로그래밍 경진대회(IUPC) 풀이
A		[BOJ 25205] 경로당펑크 2077
B		[BOJ 25206] 너의 평점은
D		[BOJ 25208] 새벽의 탐정 게임
E		[BOJ 25209] 샤카샤카
F		[BOJ 25210] 정사각형 세기
G		[BOJ 25212] 조각 케이크
H		[BOJ 25214] 크림 파스타
I		[BOJ 25215] 타이핑

1. 문제

$25208$. 새벽의 탐정 게임 (2022 인하대학교 프로그래밍 경진대회(IUPC) D번)

백준 25208번 - 새벽의 탐정 게임 (https://www.acmicpc.net/problem/25208)

2. 풀이

한 면이 뚫려있다는 조건이 없다면, 최소 이동 횟수를 구하는 평범한 BFS 문제이다. 그런데 이 조건이 추가됨에 따라서, 각 칸 (y, x)에서 뚫려있는 면의 방향에 따라 총 여섯 가지 상태가 추가로 존재하게 된다. 따라서, BFS에서 visited 배열을 3차원으로 만들어주어야 한다. (visited[N][M][6])

D를 시작점으로, R을 도착점으로 하는 BFS를 수행한다. 이때, 현재 뚫려있는 면의 방향과 현재 굴리려는 방향의 두 요소에 따라서, 다음 번에 뚫려있는 면의 방향이 결정된다. 이는 조건문을 사용하거나 배열로 한번에 관리할 수 있다.

종료 조건은 도착한 칸이 R이면서 뚫려있는 면이 바닥일 경우이다. 단, 도착한 칸이 R인데 뚫려있는 면이 바닥이 아니라면, 도둑이 바로 승리를 선언하기 때문에 이 경우는 더이상 BFS가 진행되지 않도록 해야 한다. queue에 해당 node를 집어넣지 않는다는 의미이다.

3. 채점 결과

4. 회고

칸이 R이면서 뚫려있는 면이 바닥이 아닌 경우에도 queue에 node를 담아 BFS가 계속되어버리게 구현해서 WA를 받았다.

5. 코드