[백준 / BOJ] 5427 불

문제

출처 : www.acmicpc.net/problem/5427

5427번: 불

상근이가 빌딩을  탈출하려고한다. 이때, 벽이있는곳이나 불이 붙은곳으로는 이동할수없다.

불은 1초마다 상하좌우로 번지며 벽으로는 번지지못한다.

상근이는 1초마다 상하좌우로 움직이며, 벽으로 이동하지 못한다.

가장빠르게 빌딩 밖으로 나가는 경우를 찾는 문제다.

 

풀이

BFS두번으로 풀리는 구현문제였다.

 

1. 우선, 불의 위치를 전부 저장해놓은다음, 각각의 위치를 기준으로 BFS를 돌린다.

이때 해당(y,x)지점에 불이 몇초에 도달하는지 저장해놓는다.

 

2. 그다음 상근이의 위치를 기준으로 상근이를 움직이며 BFS를 돌리는데, 이때, 벽이있거나 1번에서 저장해놓은,

상근이가 이동할려는 시간에 해당지점에 불이 번진다면 해당지점은 가지못한다. 

 

w,h범위 밖으로 가장 빠르게 언제 벗어나는지 출력하고, 벗어나지못하면 IMPOSSIBLE을 출력하면 된다.

 

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/5427%20%EB%B6%88/main.cpp

devxb/JJUNalgo