[BOJ-5427] 불(JAVA)

[BOJ-5427] 불(JAVA)

728x90

백준 5427 불

문제 설명

- 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다.

- 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

- 매 초마다, 불은 벽에 붙지 않으면서 동서남북 방향으로 인접한 빈 공간에 퍼져나간다.

- 상근이도 동서남북 인접한 칸으로 이동할 수 있고 통과할 수 없으며, 이동시 1초가 걸린다.

- 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다.

- 상근이가 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

- 빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하라.

- 각 테스트 케이스마다 빌딩을 탈출하는데 가장 빠른 시간을 출력한다. 빌딩을 탈출할 수 없으면 "IMPOSSIBLE"을 출력한다.

입력 값

- 첫째 줄에 테스트 케이스 개수가 주어진다. 테스트 케이스는 최대 100개이다.

- 각 테스트 케이스의 첫째 줄에는 빌딩 지도의 너비와 높이 w, h 가 주어진다.

( 1 <= w, h <= 1,000 )

- 다음 h개 줄에는 w개의 문자, 빌딩의 지도가 주어진다.

'.' => 빈 공간 / '#' => 벽 / '@' => 상근이의 시작 위치 / '*' => 불

- 각 지도의 @의 개수는 하나이다.

예제

문제 분석

- 이 문제에서 상근이가 이동할 수 있는 경우는 벽이 아니면서 불이 붙지 않는 빈 공간이다.

- 즉, 불보다 먼저 빈 공간에 간다면 이동할 수 있다는 것이다.

- 해당 빈 공간에 불보다 먼저 왔는지 어떻게 판단할 수 있을까?

- 간단하게 생각하면, BFS를 이용하여 알 수 있다.

- 먼저 불이 빈 공간으로 이동할 수 있는 최소 횟수를 BFS를 이용하여 구한다.

예를 들어, #*# 와 같은 빌딩이 주어지면, 불이 이동할 수 있는 최소 횟수는 #0# 와 같다.

#.# #1#

#.# #2#

- 그 이후 상근이가 빈 공간으로 이동했을 때 불보다 먼저 이동할 수 있는지를 BFS를 이용하여 구하면 된다.

- 결론적으로 정리하자면

1. BFS를 이용하여 불이 모든 공간에 이동할 수 있는 최소 이동 횟수를 구한다.

2. BFS를 이용하여 상근이가 모든 공간에 이동할 수 있는 최소 이동 횟수를 구한다.

상근이는 빈 공간에 도착했을 때 불보다 빠르게 도착하여야 한다.

3. 상근이가 모든 공간을 살펴보면서 밖으로 탈출하는 경우(빌딩 범위 밖으로 나가는 경우)에는 그 횟수를 리턴하고

모든 경우를 살펴보더라도 탈출할 수 없다면, "IMPOSSIBLE"을 리턴한다.

소스 코드

import java.io.BufferedReader; import java.io.FileInputStream; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; // https://www.acmicpc.net/problem/5427 // 불 public class Main { private static int dy[]={0,0,-1,1}; private static int dx[]={1,-1,0,0}; public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); int tc = Integer.parseInt(bf.readLine()); for(int t=0;t q = new LinkedList<>(); Pair startNode=null; for(int i=0;i= Y || nx >= X || boards[ny][nx]=='#' || fire[ny][nx] <= cnt){ continue; } fire[ny][nx]=cnt; q.add(new Pair(ny,nx)); } } q.add(startNode); int result=-1; while (!q.isEmpty() && result==-1){ Pair nowPair = q.poll(); for(int d=0;d<4;d++){ int ny = nowPair.y+dy[d]; int nx = nowPair.x+dx[d]; int cnt = visited[nowPair.y][nowPair.x]+1; if(ny < 0 || nx < 0 || ny >= Y || nx >= X ){ result=cnt; break; } if(boards[ny][nx]=='#' || visited[ny][nx] <= cnt || fire[ny][nx] <= cnt){ continue; } visited[ny][nx]=cnt; q.add(new Pair(ny,nx)); } } if(result==-1){ System.out.println("IMPOSSIBLE"); } else{ System.out.println(result); } } } static class Pair{ int y,x; public Pair(int y, int x) { this.y = y; this.x = x; } } }

from http://9327144.tistory.com/102 by ccl(A) rewrite - 2021-09-29 13:01:35