Baekjoon 5427 불 JAVA

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

5427번: 불

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%205427

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

해당 문제는 map가 주어졌을 때 상근이가 map를 탈출할 수 있는지 여부를 구하는 문제로

탈출할 수 있다면 탈출 시간을 없을 경우는 "IMPOSSIBLE"를 출력하는 문제다

map 정보는 '.' 빈 공간, '#' 벽 , '@' 상근이의 시작 위치 , '*' 불로 나타난다.

 

해당 문제는 bfs 두 개를 이용해서 해결했다.

먼저 입력 처리를 하고, 입력 처리를 진행하면서 상근이 위치와 불의 위치를 각각 큐에 저장한다.

이후 무한루프를 돌면서 아래의 동작을 진행한다.

1. 불의 큐를 bfs를 돌리면서 탐색하고 이동시킴과 동시에 새로운 불의 위치를 큐에 저장한다.

2. 상근의 큐를 bfs를 돌리면서 탐색하고 이동시킴과 동시에 새로운 불의 위치를 큐에 저장한다.

(이때 true값이 리턴되면 이미 도착한 상태라 반복문을 빠져나온다)

3. 상근이 큐와 불큐 둘 다 비었다면 갈 수 없는 상태이므로  "IMPOSSIBLE"을 출력하고 반복문을 빠져나온다.

4. 최종적으로 반복문을 빠져나오면 상근과 불 큐를 초기화해준다.

 

불 bfs에서는 처음 큐의 사이즈를 저장해서 사이즈만큼 반복하고 벽이 거나 이미 불이거나 범위를 벗어나면 빠져나오고그렇지 않으면 큐에 담고 map에 불을 확장시키는 방식으로 로직을 짰고

 

상근 bfs에서는 처음 큐의 사이즈를 저장해서 사이즈만큼 반복하고 범위를 벗어났다면 도착한 상태이므로 cnt를 반환해주고 빈 공간이 아닐 경우 이동 못하도록 하며 큐에는 좌표와 cnt+1 값을 넣고 map에는 상근이 위치를 확장시키는방식으로 로직을 짰고 상근이 위치를 map 표시해줌으로써 방문 체크를 대신하여 시간을 줄일 수 있었다.