[백준/Java] 4179번 : 불!

[문제]

지훈이는 미로에서 일을 한다. 지훈이를 미로에서 탈출하도록 도와주자!

미로에서의 지훈이의 위치와 불이 붙은 위치를 감안해서 지훈이가 불에 타기전에 탈출할 수 있는지의 여부, 그리고 얼마나 빨리 탈출할 수 있는지를 결정해야한다.

지훈이와 불은 매 분마다 한칸씩 수평또는 수직으로(비스듬하게 이동하지 않는다) 이동한다.

불은 각 지점에서 네 방향으로 확산된다.

지훈이는 미로의 가장자리에 접한 공간에서 탈출할 수 있다.

지훈이와 불은 벽이 있는 공간은 통과하지 못한다.

[조건]

• 시간 제한 : 1초
• 메모리 제한 : 256MB

[입력]

입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다.

다음 입력으로 R줄동안 각각의 미로 행이 주어진다.

각각의 문자들은 다음을 뜻한다.

• #: 벽
• .: 지나갈 수 있는 공간
• J: 지훈이의 미로에서의 초기위치 (지나갈 수 있는 공간)
• F: 불이 난 공간

J는 입력에서 하나만 주어진다.

[출력]

지훈이가 불이 도달하기 전에 미로를 탈출 할 수 없는 경우 IMPOSSIBLE 을 출력한다.

지훈이가 미로를 탈출할 수 있는 경우에는 가장 빠른 탈출시간을 출력한다.

[문제 풀이]

• 불과 지훈이 배열을 따로 따로 BFS
• 불의 경우 일반적인 BFS 수행
• 지훈의 경우 BFS + 불보다 더 빨리 도착해야하는 조건 고려

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

class miro{
	int r;
	int c;
	
	miro(int r, int c){
		this.r = r;
		this.c = c;
	}
}

public class boj_4179_불 {
	static BufferedReader br;
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer(br.readLine());
        int R = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int[][] arr = new int[R][C]; // 불 배열
        int[][] arr2 = new int[R][C]; // 지훈 배열
        Queue<miro> queue = new LinkedList<>(); // 불
        Queue<miro> queue2 = new LinkedList<>(); // 지훈
        for(int r=0; r<R; r++) {
            String str = br.readLine();
            for(int c=0; c<C; c++) {
                arr[r][c] = str.charAt(c);
                if(arr[r][c]==70) { // F
                	queue.add(new miro(r, c));
                	arr[r][c] = 1;
                	arr2[r][c] = 0;
                } else if(arr[r][c]==74) { // J
                	queue2.add(new miro(r, c));
                	arr[r][c] = 0;
                	arr2[r][c] = 1;
                } else if(arr[r][c]==35) { // #
                	arr[r][c] = -1;
                	arr2[r][c] = -1;
                } else { // .
                	arr[r][c] = 0;
                	arr2[r][c] = 0;
                }
            }
        }
        
        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        
        // 불
		while(!queue.isEmpty()) {
        	for(int d=0; d<4; d++) {
        		int nr = queue.peek().r+dr[d];
        		int nc = queue.peek().c+dc[d];
        		if(nr>=0 && nr<R && nc>=0 && nc<C && arr[nr][nc]==0) {
        			arr[nr][nc] = arr[queue.peek().r][queue.peek().c]+1;
        			queue.add(new miro(nr, nc));
        		}
        	}
        	queue.poll();
        }
		
		// 지훈
		while(!queue2.isEmpty()) {
        	for(int d=0; d<4; d++) {
        		int nr = queue2.peek().r+dr[d];
        		int nc = queue2.peek().c+dc[d];
        		// 범위 벗어날 경우 탈출 성공
        		if(nr<0 || nr>=R || nc<0 || nc>=C) {
        			System.out.println(arr2[queue2.peek().r][queue2.peek().c]);
        			return;
        		}
        		
        		// 방문 X
        		if(arr2[nr][nc]==0) {
        			// 불이 도달하지 못한 곳이거나, 내가 더 빠를 경우 지나감
        			if(arr[nr][nc]==0 || arr[nr][nc]>(arr2[queue2.peek().r][queue2.peek().c]+1)) {
        				arr2[nr][nc] = arr2[queue2.peek().r][queue2.peek().c]+1;
        				queue2.add(new miro(nr, nc));
        			}
        			// 불이 더 빠를 경우 벽처리
        			else {
        				arr2[nr][nc] = -1;
        			}
        		}
        	}
        	queue2.poll();
        }
		
		System.out.println("IMPOSSIBLE");        
    }
}

 

[소감]

• 단순히 불보다 빨리 도착하는 조건만을 고려해 수행
• 불이 도달하지 못하는 경우가 있으며, 수많은 반례를 고려해야함

 

출처 : 백준 https://www.acmicpc.net/problem/4179