[백준 BOJ] 5427 - 불

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

5427번: 불

입력

• 상근이의 위치와 불의 위치를 각각 큐에 저장하였다.
• 테스트 케이스가 있는 문제이므로, 테스트 케이스의 결과를 출력한 뒤 상근이의 위치가 저장되어있는 큐와 불의 위치가 저장되어 있는 큐를 초기화 시켜주었다. 또한 방문배열, 전체 배열도 초기화 시켰다.

구현 

• 상근이와 불은 동시에 번지고, 불이 번질 곳에는 상근이가 이동하지 못한다는 조건이 있기 때문에 불을 먼저 이동시켰다.
  • 원래는 불이 번질 위치만 저장해두고 상근이를 먼저 이동시켰는데 불필요한 작업이 들어가는 것으로 생각한다. 또한, 시간초과가 날 수 있다
• 불의 확산은 bfs 탐색을 사용하였다. 
  
  • 이때, 이미 불이 번진 곳에도 불을 확산시켰더니 시간초과가 났었다
• 상근이의 이동 또한 bfs 탐색을 사용하였다.(불의 확산과 똑같음)
  • 상근이가 이동하기 전, 탈출 조건을 먼저 확인하였다.
  • 탈출조건은 상근이가 map의 가장자리에 위치하면 탈출이다. 이때도 1초가 지나고 상근이가 이동하는 것이므로 출력 시 1을 더해주었다.
  • 상근이가 이동했다면, is_move 라는 flag 변수를 두어, 이동하지 못한 경우에는 IMPOSSIBLE를 출력할 수 있도록 하였다.

소스 코드