[JAVA][BOJ][G4] 5427. 불

5427번: 불

문제

상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다.

매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다.

빌딩의 지도가 주어졌을 때, 얼마나 빨리 빌딩을 탈출할 수 있는지 구하는 프로그램을 작성하시오.

입력

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

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

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

• '.': 빈 공간
• '#': 벽
• '@': 상근이의 시작 위치
• '*': 불

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

출력

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

풀이

bfs를 두 개 만들어서 풀 수 있는 문제다 처음에는 상근이의 이동을 dfs로 풀어 보려고 했지만 예제만 잘 돌아가고 정답은 자꾸 틀리게 나와서 bfs로 수정했다 dfs로 짠 코드는 주석을 달아 남겨두었다 bfs로 하더라도 visited를 해 주지 않으면 메모리 초과가 나기 때문에 조심해야 한다

코드

import java.io.*;
import java.util.*;

public class G4_5427_불 {
	static int w, h, ans;
	static char[][] arr;
	static boolean[][] visited;
	static int[] dx = {-1, 1, 0, 0};
	static int[] dy = {0, 0, -1, 1};
	static Queue<int[]> fire;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			w = Integer.parseInt(st.nextToken());
			h = Integer.parseInt(st.nextToken());
			
			arr = new char[h][w];
			visited = new boolean[h][w];
			fire = new ArrayDeque<>();
			
			int x = 0, y = 0;
			
			for (int i = 0; i < h; i++) {
				String str = br.readLine();
				for (int j = 0; j < w; j++) {
					arr[i][j] = str.charAt(j);
					if(arr[i][j] == '@') {
						x = i;
						y = j;
					} else if(arr[i][j] == '*') {
						fire.add(new int[] {i, j});
					}
				}
			}
			
			ans = 0;
			bfs(x, y);
			
			if(ans!=0) sb.append(ans).append("\n");
			else sb.append("IMPOSSIBLE\n");
			
		}
		
		System.out.println(sb);
	}
	
	

private static void bfs(int x, int y) {
		Queue<int[]> queue = new ArrayDeque<>();
		queue.add(new int[] {x, y});
		visited[x][y] = true;
		
		int[][] time = new int[h][w];
		
		while(!queue.isEmpty()) {
			fire();
			int cnt = queue.size();
			for (int c = 0; c < cnt; c++) {
				int[] tmp = queue.poll();
				for (int k = 0; k < 4; k++) {
					int i = tmp[0] + dx[k];
					int j = tmp[1] + dy[k];
					
					if(i<0 || i>=h || j<0 || j>=w) {
						ans = time[tmp[0]][tmp[1]] + 1;
						return;
					}
					
					if(visited[i][j] || arr[i][j] == '#' || arr[i][j] == '*') continue;
					
					arr[i][j] = '@';
					queue.add(new int[] {i, j});
					time[i][j] = time[tmp[0]][tmp[1]] + 1;
					visited[i][j] = true;
				}
			}
		}
		
	}



//	private static void dfs(int x, int y, int time) {
//		
//		fire();
//		
//		for (int k = 0; k < 4; k++) {
//			int i = x + dx[k];
//			int j = y + dy[k];
//			
//			if(i<0 || i>=h || j<0 || j>=w) {
//				ans = time + 1;
//				return;
//			}
//			
//			if(visited[i][j] || arr[i][j] == '#' || arr[i][j] == '*') continue;
//			
//			if(arr[x][y] != '*') arr[x][y] = '.';
//			arr[i][j] = '@';
//			visited[i][j] = true;
//			dfs(i, j, time+1);
//			visited[i][j] = false;
//		}
//	}

	private static void fire() {
		int cnt = fire.size();
		
		for (int i = 0; i < cnt; i++) {
			int[] tmp = fire.poll();
			
			for (int k = 0; k < 4; k++) {
				int x = tmp[0] + dx[k];
				int y = tmp[1] + dy[k];
				
				if(x<0 || x>=h || y<0 || y>=w || arr[x][y] == '*' || arr[x][y] == '#') continue;
				
				arr[x][y] = '*';
				fire.add(new int[] {x, y});
			}
		}
		
	}

}

결과

 

#자바 #java #boj #백준 #알고리즘