4179 - 불!

정보

• 문제 보기: 4179 - 불!
• 소요 시간: 47분 19초
• 풀이 언어: java
• 체감 난이도: 3️⃣~4️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

bfs

풀이 코드

정보

• 메모리: 58084 KB
• 시간: 520 ms

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

public class Main
{
    static int r, c;
    static int[][] miro;
    static boolean[][] fvisited;
    static boolean[][] jvisited;
    static Deque<int[]> fq = new ArrayDeque<>();
    static Deque<int[]> jq = new ArrayDeque<>();
    static int[] dy = {-1, 0, 0, 1};
    static int[] dx = {0, -1, 1, 0};
    
    public static int bfs() {
        // queue init was done in input()
        int time = 1;
        
		while (!jq.isEmpty()) { // until J evacuate
	        while (!fq.isEmpty() && fq.peek()[2] == time) {
    		    int[] fpos = fq.pop();
    		    for (int d = 0; d < 4; ++d) {
    		        int nfy = fpos[0] + dy[d];
    		        int nfx = fpos[1] + dx[d];
    		        if (nfy < 0 || r <= nfy || nfx < 0 || c <= nfx) continue; // out of bound
    		        if (fvisited[nfy][nfx] || miro[nfy][nfx] == 1) continue;
    		        fvisited[nfy][nfx] = true;
    		        fq.add(new int[]{nfy, nfx, time+1});
    		    }
	        }
		    
		    while (!jq.isEmpty() && jq.peek()[2] == time) {
    		    int[] jpos = jq.pop();
    		    for (int d = 0; d < 4; ++d) {
    		        int njy = jpos[0] + dy[d];
    		        int njx = jpos[1] + dx[d];
    		        if (njy < 0 || r <= njy || njx < 0 || c <= njx) return time; // evacuate
    		        if (fvisited[njy][njx] || jvisited[njy][njx] || miro[njy][njx] == 1) continue;
    		        jvisited[njy][njx] = true;
    		        jq.add(new int[]{njy, njx, time+1});
    		    }
		    }
		    ++time;
		}
		
		return -1;
    }
    
	public static void main(String[] args) throws IOException {
		input();
		int ans = bfs();
		System.out.println(ans == -1 ? "IMPOSSIBLE" : ans);
	}
	
	public static void input() throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    r = Integer.parseInt(st.nextToken());
	    c = Integer.parseInt(st.nextToken());
	    miro = new int[r][c];
	    fvisited = new boolean[r][c];
	    jvisited = new boolean[r][c];
	    
	    for (int i = 0; i < r; ++i) {
	        char[] line = br.readLine().toCharArray();
	        for (int j = 0; j < c; ++j) {
	            miro[i][j] = line[j] == '#' ? 1 : 0;
	            if (line[j] == 'J') {
                    jq.add(new int[]{i, j, 1});
                    jvisited[i][j] = true;
	            }
	            else if (line[j] == 'F') {
	                fq.add(new int[]{i, j, 1});
	                fvisited[i][j] = true;
	            }
	        }
	    }
	}
}

풀이 해설

구현은 어렵지 않은데 corner case 종합 선물세트같은 문제이다.

주어진 맵에서 지훈이가 불에 안타고 무사 탈출이 가능한지 닥터 스트레인지마냥 탐색해보아야 한다.

최단 시간을 출력해야하므로 bfs를 사용해야 한다는 것은 자동으로 떠오르게 된다.

⚠️ 실수하기 쉬운 반례

다음의 케이스를 조심해야 한다.

CASE 1

불은 0 ~ n개가 주어질 수 있다.

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

👉 문제를 잘 읽자. J는 조건을 명확하게 했지만 F에 대해선 아무 말이 없다. (=낚시질)

5 5
#####
#J.F#
#..F#
#...#
#...#

4

5 5
#####
#J.F#
#...#
#..F#
#...#

IMPOSSIBLE

CASE 2

불과 지훈이가 같은 지점에 동시 도착하면 지훈이가 타버린다.

불 bfs를 먼저 진행해야할까, 지훈 bfs를 먼저 진행해야할까?

불을 먼저 진행하는 것이 좋다. 어차피 동시 도착하는 지점은 무효한 탈출경로가 되기 때문에

애당초 bfs 큐에 안넣는 것이 최적의 선택일 것이다.

CASE 3

시작부터 지훈이가 경계에 있는 경우

풀이 코드처럼

if (njy < 0 || r <= njy || njx < 0 || c <= njx) return time; // evacuate

이렇게 탈출 조건을 out-bound 기준으로 세웠다면 시작부터 경계에 있는 경우를 따로 처리해줄 필요가 없다.

하지만 y가 0 또는 r-1, x가 0 또는 c-1 인 경우로 탈출 조건을 세웠다면, 이를 ny, nx로 판단하면 안되기에

bfs에서 while 들어가기 전 초기값을 한번 검사해주는 별도의 로직이 필요해진다.

1 3
J#F

1

메모

• 더블 bfs는 웬만하면 while 안에 while 2개 돌아간다고 템플릿 잡아놓기
• 다시는 while (!q.isEmpty()) 로직 내부에 while (q.peek()[2] == ...) 로직 넣는 실수하지 마쇼 이건 경고요...
  • q.pop() 하다가 peek에서 널익셉션 터짐 T~T