문제 풀이

BFS로 풀이할 수 있는 문제이다.

불의 위치를 먼저 큐에 넣고, 마지막에 상근이의 위치를 넣어줘야한다.
불을 먼저 큐에 넣어줘서 불이 있는 번지는 곳에 사람이 갈 수 없도록 해야한다.
나는 실수로 상근이의 위치를 마지막에 넣어주지 않아서 문제가 있었다.

그리고 각 테스트 케이스마다 큐는 초기화 시켜주어야한다.

불이 이미 번진 곳에는 상근이가 이동하거나, 불을 번지게 할 필요가 없다. 그러므로 큐에 넣지 않는다.

visit 배열은 이동거리 체크 및 방문 체크용으로 사용한다.
상근이의 이동거리는 이전까지 이동거리 + 1, 즉 visit[ny][nx] = visit[cur.y][cur.x] + 1 이다.

answer이 -1로 초기화 되어있는데, 상근이가 가장자리 부분에 위치해 있다면 상근이의 이동거리 + 1을 answer로 하고 출력하면 된다.
bfs를 모두 돌았는데 조건에 맞는 답을 찾지 못해 여전히 -1이라면 "IMPOSSIBLE"을 출력한다.

문제 링크

boj/5427

소스코드

PS/5427.java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

  static class Point {
    int x, y;
    public Point(int x, int y) {
      this.x = x;
      this.y = y;
    }
  }

  static Queue<Point> q = new LinkedList<>();
  static int[][] visit = new int[1001][1001];
  static int[] dx = {0, 1, 0, -1};
  static int[] dy = {1, 0, -1, 0};

  public static void main(String[] args) throws Exception {
    int T = Integer.parseInt(br.readLine());
    char[][] map = new char[1001][1001];
    for (int i = 0; i < T; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      int c = Integer.parseInt(st.nextToken());
      int r = Integer.parseInt(st.nextToken());
      int answer = -1;
      int sx = 0, sy = 0;
      for (int j = 0; j < r; j++) {
        map[j] = br.readLine().toCharArray();
        for (int k = 0; k < c; k++) {
          visit[j][k] = -1;
          if (map[j][k] == '*') {
            visit[j][k] = 0;
            q.add(new Point(k, j));
          } else if (map[j][k] == '@') {
            visit[j][k] = 0;
            sy = j;
            sx = k;
          }
        }
      }
      q.add(new Point(sx, sy));
      while (!q.isEmpty()) {
        Point cur = q.poll();
        if (map[cur.y][cur.x] != '*' && (cur.x == 0 || cur.x == c - 1 || cur.y == 0 || cur.y == r - 1)) {
          answer = visit[cur.y][cur.x] + 1;
          break;
        }
        for (int dir = 0; dir < 4; dir++) {
          int nx = cur.x + dx[dir];
          int ny = cur.y + dy[dir];

          if (ny >= 0 && nx >= 0 && nx < c && ny < r && visit[ny][nx] == -1 && map[ny][nx] != '#') {
            if ((map[cur.y][cur.x] != '*' && map[ny][nx] == '*') ||  map[ny][nx] == '*') {
              continue;
            }
            if (map[cur.y][cur.x] == '*') {
              map[ny][nx] = '*';
            } else {
              map[ny][nx] = '@';
            }
            q.add(new Point(nx, ny));
            visit[ny][nx] = visit[cur.y][cur.x] + 1;

          }
        }
      }
      if (answer == -1) {
        System.out.println("IMPOSSIBLE");
      } else {
        System.out.println(answer);
      }
      q.clear();
    }
  }

}