BOJ 5427번 불 문제 자바(java) 풀이
문제 정리
- 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있고, 불이 번져서 출구를 향해 뛰고 있다.
- 매 초마다 불은 동서남북 인접한 빈 공간으로 퍼져나간다.
- 벽에는 불이 붙지 않는다.
- 상근이는 동서남북 인접한 칸으로 이동할 수 있다. 이동하는데 1초가 걸린다.
- 상근이는 벽이 있거나 불이 번졌으면 갈 수 없다.
- 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다!!!!
- 문자
- #: 벽
- .: 지나갈 수 있는 공간
- @: 상근이의 미로에서의 초기위치(지나갈 수 있는 공간)
- *: 불이난 공간
- 불이 도달하기 전에 미로를 탈출할 수 없는 경우 'IMPOSSIBLE' 출력
- 탈출할 수 있는 경우 가장 빠른 탈출시간 출력
문제 접근
5427번 문제와 4179번 문제가 같습니다. 그러므로 좀더 포괄적인 5427번 문제를 기준으로 설명 드리겠습니다.
'빠른 시간'에 관련된 문제이므로 그래프 문제로 접근하여 너비 우선 탐색(bfs)을 이용합니다. dfs로 작성한 경우 역시 시간초과가 나왔습니다. 가지치기를 아주 잘한다면 가능할지도??
visited 배열을 이용하여 불이 번짐(-1)과 벽(-1), 상근이의 이동(1)을 표시합니다.
상근이가 방문한 곳과 불이 번진 곳을 다르게 표시하는 이유는 상근이가 이동 한 곳에 불이 퍼질 수 있기 때문에 다르게 하였습니다.
상근이가 움직이기 전에 그 위치가 불이 퍼진 곳과 같은 표시로 방문처리 되어 있다면, 그 부분은 불이 퍼질 수 없기 때문입니다.
- 위치와 시간을 담을 Pos Class를 생성합니다.
- 불의 초기 위치를 queue에 넣고 visited 배열을 초기화 합니다.
이때 가로세로 크기를 2씩 크게 합니다. 상근이가 밖으로 나감을 쉽게 확인하기 위해서 입니다. (이렇게 하지 않으면 0번째 index를 참조하기 때문에 불편)
즉 빌딩 배열 사방을 둘러싸는 상근이가 탈출할 수 있는 공간을 만드는 것입니다.
- bfs 탐색을 시작합니다. 상근이가 방문하는 위치는 1로 표시합니다.
- 불을 먼저 퍼뜨립니다. 불이 있는 곳은 상근이가 갈 수 없기 때문입니다. 그리고 불이 붙은 곳은 -1로 표시합니다.
- 불을 퍼뜨리고 상근이가 이동을 시작합니다. 상근이가 방문하지 않았거나(visited != 1) 불이 번지지 않았다면(visited != -1) 이동합니다.
- 그러다가 추가적으로 만든 공간에 도달하였다면(맨 끝쪽) 최소값을 갱신해줍니다.
- 이를 상근이의 위치를 담은 queue가 빌때 까지 반복합니다.
- 최소값이 MAX_VALUE와 같다면 끝에 도달하지 못한 경우이므로 IMPOSSIBLE을 출력하고 그렇지 않다면 min 값을 출력합니다.
(BFS)백준 5427번 불 자바 코드