[Unsolved][JAVA] 백준 4179 불!

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

4179번: 불!

 

1. 서론

 

그 유명한 불! 문제를 이제야 풀어보다... 엄청 쉬워 보였으나 쉽지 않았다... BFS 문제이다.

 

2. 문제 풀이

 

문제 자체는 아주 심플하다.

 

2차원 배열이 주어지고 지훈이가 서있는 곳은 J, 불이 있는 곳은 F, 벽인 곳은 #, 그 외의 빈공간은 .으로 주어진다. 

이때 불과 지훈이는 각 분마다 동서남북으로 이동이 가능하다. 하지만 벽인 곳은 불과 지훈이 둘다 이동할 수 없다.

배열의 가장자리 밖으로 나가면 탈출이라고 가정했을때, 탈출에 걸리는 최소시간을 구하는 문제이다.

이때 불을 피해 가장자리로 갈 수 없는 경우라면 IMPOSSIBLE이라고 출력한다.

 

현재 위치에서 이동해 최소시간을 구하는 문제... 아주 전형적인 BFS 문제이다.

그러나? 문제는 평소와는 다르게 이동주체가 지훈이 한 명이 아니라 불까지 두 개나 있다.

처음에는 그냥 큐에서 값을 하나씩 뺄때마다 불을 이동시키면 되겠지? 생각했는데 틀렸다.

그래서 어떻게 하면 이동 레벨 단위로(날) 단위로 불을 옮길 수 있을까 생각했는데 클래스를 만들어서 2차원 배열을 값으로 넣자. 그러면 좌표값과 2차원 배열값이 같이 set로 있으니까 불 번지는 값이 이동단위 별로 움직이니까 맞겠지?라고 생각했는데 값이 다 맞았는지 틀렸는지 알 새도 없이 메모리 초과가 뜨고 말았다. 그렇다... 매번 2차원 배열을 움직이는 수만큼 저장하려니까 터지고 만 것이다.

 

결국 난... 인터넷을 찾아 가장 이해하기 쉬운 코드로 풀게 되었다.

 

출처: https://sundries-in-myidea.tistory.com/86#recentComments

[백준 - 4179번] 불! - 자바(JAVA) 정리 및 해설

 

이 문제의 핵심은 지훈이 이동이야 뻔하고 불을 어떻게 이동시키냐이다.

나는 그걸 따로하려다가, 클래스를 만들어서 set로 묶었다가 실패했는데 결국 답은 그냥 지훈이처럼 똑같이 큐를 통해서 이동하는 것이었다.

불은 현재 불이 위치한 곳을 기준으로 벽이 있는 곳을 제외하고 동서남북으로 뻗어나간다. 그러기 위해서 매 분, 즉 한 바퀴를 돌 때마다 딱 현재 맵 위에 불이 위치한 수만큼만 불을 동서남북으로 이동하면 되는 것이다. 그리고 지훈이와 불이 동시에 이동해야 하기 때문에, 불을 먼저 이동시켜 준다. 왜냐하면 지훈이가 먼저 이동하면 지훈이가 있는 자리에 불이 번지는 경우를 커버할 수 없기 때문이다.(고립되는 경우)

그리고 포인트는 각각의 큐들이 빌 때까지 이동하는게 아니라 분단위로 측정해야 하기 때문에 각 분마다 존재하는 불의 수, 지훈이의 수(case)만큼 이동시킨 후 지훈이가 범위 밖으로 이동하는 순간, 반복문이 반복된 횟수가 최솟값이 되는 것이다.

 

3. 코드 설명

 

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {

  static int r, c;
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(br.readLine());
    r = Integer.parseInt(st.nextToken());
    c = Integer.parseInt(st.nextToken());

    char[][] map = new char[r][c];
    Queue<Point> jq = new ArrayDeque<>(); //지훈이
    Queue<Point> fq = new ArrayDeque<>(); //불

    for (int i = 0; i < r; i++) {
      String s = br.readLine();
      map[i] = s.toCharArray();
      for (int j = 0; j < c; j++) {
        if (map[i][j] == 'J')
          jq.add(new Point(i, j));
        if (map[i][j] == 'F')
          fq.add(new Point(i, j));
      }
    }

    int ans = 0;
    int[] dx = {0, -1, 1, 0}, dy = {1, 0, 0, -1};
    while (true) {
      ans++; //분

      int size = fq.size(); //각 분 당 가지고 있는 불의 수
      while (size > 0) { //불 확산
        size--;
        Point p = fq.poll();
        for (int k = 0; k < 4; k++) {
          int nx = p.x + dx[k], ny = p.y + dy[k];
          if (range(nx, ny) && (map[nx][ny] == '.' || map[nx][ny] == 'J')) { //지훈이가 있거나 불이 없는 곳에만
            map[nx][ny] = 'F';
            fq.add(new Point(nx, ny));
          }
        }
      }

      size = jq.size(); //각 분 당 지훈이 이동
      while (size > 0) {
        size--;
        Point p = jq.poll();
        for (int k = 0; k < 4; k++) {
          int nx = p.x + dx[k], ny = p.y + dy[k];
          if (!range(nx,ny)) { //지훈이가 범위 밖으로 이동할 수 있다면, 즉 탈출완료 했다면
            System.out.print(ans);
            return;
          }
          if (range(nx, ny) && map[nx][ny] == '.') {//빈 곳으로만 이동
            map[nx][ny] = 'J';
            jq.add(new Point(nx, ny));
          }
        }
      }
      if (jq.isEmpty()) {//어디로도 이동할 수 없다면
        System.out.print("IMPOSSIBLE");
        return;
      }
    }
  }
  public static boolean range(int nx, int ny) {
    if (nx >= 0 && nx < r && ny >= 0 && ny < c) return true;
    return false;
  }
}

 

지훈이 있는 곳까지도 불이 이동하나 헷갈렸는데 벽이 아닌 경우는 다 이동 가능하므로 가능한 것으로 결론짓고 문제를 풀었다.

전체 반복문을 돌면서 불과 지훈이를 이동시키고 지훈이가 가장자리에 도달했다면, 그 반복한 시간을 출력하고, 더 이동 가능한 지훈이가 없다면 IMPOSSIBLE을 출력하게 해줬다.