[백준] 3055번 - 탈출

3055번 - 탈출

[문제]

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

3055번: 탈출

 

[문제 풀이]

D	.	*
.	.	.
.	S	.

D	*	*
.	S	*
S	S	S

D	*	*
S	S	*
S	S	S

위 표는 고슴도치가 비버의 굴을 찾아가는 과정이다.

1분에 빈칸(.)으로 한 칸씩 이동이 가능하며, 물(*)도 1분에 한 칸씩 채워진다. 

물이 채워진 곳과 고슴도치의 위치를 나타내기 위해 2개의 Queue(water - 물, queue - 고슴도치)를 사용하였다. 

(경로를 구하는 문제이기 때문에 dx, dy 배열을 사용하여 상하좌우로 이동할 수 있도록 구현하였다.)

고슴도치는 물이 찰 예정인 칸으로 이동하지 못하기 때문에 water 큐를 사용하여 물이 채워질 칸을 먼저 구하였다. 

그다음 고슴도치가 이동할 수 있는 칸을 구하였다. 고슴도치가 이동했을 때 해당 칸이 비버의 굴(D)이면 탐색을 멈춘다. 

 

[주요 코드]

빈 칸에 물이 채워지는 과정

고슴도치의 이동 경로

 

[전체 코드]

 

 

2023.06.21