BOJ - 불! 4179번 (JAVA)

❓ 문제 - 백준 불! 4179번 - JAVA 풀이법

 

출처 

(https://www.acmicpc.net/problem/4179)

4179번: 불!

 

 

📝 문제해결법

1. 이 문제는 BFS로 해결했다.

• 불이 4방향 이동 -> 지훈이의 이동의 순서대로 진행되는 것이 이 문제의 포인트이다.
• 방문처리는 따로 visited 배열로 하지 않고 map 2차원 배열에 F, J로 변경시켜줘서 방문을 체크했다.
• 불이 4방향으로 이동할 때 범위 넘지 않고, 벽이 아닌 곳, 그리고 이미 불이 퍼진 곳을 제외하고 이동시켰다.
• 지훈이도 4방향으로 이동할 때 그 위치에서 만약 범위를 넘는 곳이라면 가장자리이므로 탈출의 조건이므로 탈출 시간을 업데이트 후에 BFS를 빠져와서 정답을 출력하도록 했다.

 

2. 느낀점

• 사실,, 테케 하나만 보고,, 이게 왜 3일까 계속 고민했던 문제! 하지만 찾아보니 불의 이동이 먼저라는 조건이 문제에 주어지지 않았지만 테케를 통해 예측해야했다..
• 다음에 이런 경우가 생기면 순서를 다시 한번 생각해서 테케를 맞춰봐야겠다고 느꼈다.

 

💻 소스코드 (JAVA)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Time;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int n, m, ans;
	public static int[] dx = {-1, 1, 0, 0};
	public static int[] dy = {0, 0, -1, 1};
	public static char[][] map;
	public static class Node {
		int x;
		int y;
		int time;
		public Node(int x, int y, int time) {
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}
	public static Queue<Node> jh, fire;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		jh = new LinkedList<>();
		fire = new LinkedList<>();
		
		
		map = new char[n][m];
		for(int i=0;i<n;i++) {
			map[i] = br.readLine().toCharArray();
			for(int j=0;j<m;j++) {
				if(map[i][j] == 'J') {
					jh.add(new Node(i, j, 0));
				}
				
				if(map[i][j] == 'F') {
					fire.add(new Node(i, j, 0));
				}
			}
		}
		
		ans = 0;
		
		if(bfs()) {
			System.out.println("IMPOSSIBLE");
		} else {
			System.out.println(ans);
		}
	
		
		
		
	}
	
	public static boolean bfs() {
		// 불 먼저
		while(!jh.isEmpty()) {
			int f_size = fire.size();
			for(int i=0;i<f_size;i++) {
				Node node = fire.poll();
				
				for(int d=0;d<4;d++) {
					int nx = node.x + dx[d];
					int ny = node.y + dy[d];
					if(0 <= nx && nx < n && 0 <= ny && ny < m) {
						if(map[nx][ny] != '#' && map[nx][ny] !='F') {
							map[nx][ny] = 'F';
							fire.add(new Node(nx, ny, node.time+1));
						}
					} 
				}
				
			}
			
			int j_size = jh.size();
			
			for(int i=0;i<j_size;i++) {
				Node node = jh.poll();
				
				for(int d=0;d<4;d++) {
					int nx = node.x + dx[d];
					int ny = node.y + dy[d];
					if(nx < 0 || nx >= n || ny < 0 || ny >= m) {
						ans = node.time+1;
						return false;
					}
					
					
					if(map[nx][ny] != '#' && map[nx][ny] !='F' && map[nx][ny] != 'J') {
							jh.add(new Node(nx, ny, node.time+1)); 
							map[nx][ny] = 'J';
					}
					
				}
				
			}
			
		}
		return true;

	}

}