불!(BJ_G3_4179)

1. 문제 링크

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

 

---

 

2. 나의 코드

메모리: 72472kb
시간: 656ms
코드 길이: 3254B
시간 복잡도 : O(R∗C)
설명:
- 지훈이의 이동과 불의 이동을 따로 큐에 저장한다.
- 매 분마다 불을 먼저 이동시킨 후 지훈이를 이동시킨다.

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

public class BJ_4179 {

    static class Coordinate {
        int r, c;
        int cnt;

        public Coordinate(int r, int c, int cnt) {
            this.r = r;
            this.c = c;
            this.cnt = cnt;
        }
    }

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int R, C;
    static char[][] map;
    static boolean[][] visited;
    static Queue<Coordinate> manList;
    static Queue<Coordinate> fireList;

    public static void main(String[] args) 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());
        map = new char[R][C];
        visited = new boolean[R][C];
        manList = new LinkedList<>();
        fireList = new LinkedList<>();
        for (int i = 0; i < R; i++) {
            String s = br.readLine();
            for (int j = 0; j < s.length(); j++) {
                map[i][j] = s.charAt(j);
                if (map[i][j] == 'J') {
                    manList.add(new Coordinate(i, j, 1));
                    map[i][j] = '.';
                    visited[i][j] = true;
                } else if (map[i][j] == 'F') {
                    fireList.add(new Coordinate(i, j, 1));
                }
            }
        }
        bfs();
    }

    public static void bfs() {
        while (!manList.isEmpty()) {
            // 불 이동
            for (int i = 0, size = fireList.size(); i < size; i++) {

                Coordinate nowFire = fireList.poll();

                for (int d = 0; d < 4; d++) {
                    int nr = nowFire.r + dx[d];
                    int nc = nowFire.c + dy[d];

                    if (isValid(nr, nc) && map[nr][nc] == '.') {
                        fireList.add(new Coordinate(nr, nc, nowFire.cnt + 1));
                        map[nr][nc] = 'F';
                    }
                }
            }
            // 지훈이 이동
            for (int i = 0, size = manList.size(); i < size; i++) {
                
                Coordinate nowMan = manList.poll();
                
                if (isEscape(nowMan.r, nowMan.c)) {
                    System.out.println(nowMan.cnt);
                    return;
                }
                
                for (int d = 0; d < 4; d++) {
                    int nr = nowMan.r + dx[d];
                    int nc = nowMan.c + dy[d];

                    if (isValid(nr, nc) && !visited[nr][nc] && map[nr][nc] == '.') {
                        manList.add(new Coordinate(nr, nc, nowMan.cnt + 1));
                        visited[nr][nc] = true;
                    }
                }
            }
        }
        System.out.println("IMPOSSIBLE");
    }

    public static boolean isValid(int r, int c) {
        return (r >= 0 && r < R && c >= 0 && c < C);
    }

    public static boolean isEscape(int r, int c) {
        return r == 0 || r == R - 1 || c == 0 || c == C - 1;
    }
}

 

---

 

3. 정답 코드

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

class Pair {

  int X, Y;

  Pair(int X, int Y) {
    this.X = X;
    this.Y = Y;
  }
}

public class baekjoon4179 {

  static int n, m;
  static char[][] board;
  static int[][] dist1; // 불의 전파 시간
  static int[][] dist2; // 지훈이의 이동 시간
  static int[] dx, dy;
  static Queue<Pair> Q1;
  static Queue<Pair> Q2;

  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());

    board = new char[n][m];
    dist1 = new int[n][m]; // 불의 전파 시간
    dist2 = new int[n][m]; // 지훈이의 이동 시간
    Q1 = new LinkedList<>();
    Q2 = new LinkedList<>();
    dx = new int[] { 1, 0, -1, 0 };
    dy = new int[] { 0, 1, 0, -1 };

    // 배열 초기화
    for (int i = 0; i < n; i++) {
      String s = br.readLine();
      for (int j = 0; j < m; j++) {
        board[i][j] = s.charAt(j);
        dist1[i][j] = -1;
        dist2[i][j] = -1;
        if (board[i][j] == 'F') {
          Q1.offer(new Pair(i, j));
          dist1[i][j] = 0;
        }
        if (board[i][j] == 'J') {
          Q2.offer(new Pair(i, j));
          dist2[i][j] = 0;
        }
      }
    }
    // 불에 대한 BFS
    while (!Q1.isEmpty()) {
      Pair cur = Q1.poll();
      for (int dir = 0; dir < 4; dir++) {
        int nx = cur.X + dx[dir];
        int ny = cur.Y + dy[dir];
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
        if (dist1[nx][ny] >= 0 || board[nx][ny] == '#') continue;
        dist1[nx][ny] = dist1[cur.X][cur.Y] + 1;
        Q1.offer(new Pair(nx, ny));
      }
    }

    // 지훈이에 대한 BFS
    while (!Q2.isEmpty()) {
      Pair cur = Q2.poll();
      for (int dir = 0; dir < 4; dir++) {
        int nx = cur.X + dx[dir];
        int ny = cur.Y + dy[dir];
        // 범위를 벗어났다는 것은 탈출에 성공했다는 의미
        if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
          System.out.println(dist2[cur.X][cur.Y] + 1);
          return;
        }
        if (dist2[nx][ny] >= 0 || board[nx][ny] == '#') continue;
        // 불의 전파 시간을 조건에 추가
        if (dist1[nx][ny] <= dist2[cur.X][cur.Y] + 1) continue;
        dist2[nx][ny] = dist2[cur.X][cur.Y] + 1;
        Q2.offer(new Pair(nx, ny));
      }
    }

    System.out.println("IMPOSSIBLE");
  }
}

 

---

 

4. 배운 점

- 이 문제는 BFS를 활용한 구현문제이다.

- 가장 큰 핵심은 같은 시간안에 지훈이와 불을 이동시켜야 한다.