[백준/2206] 벽 부수고 이동하기 (Java)

Question

• 문제 링크 : https://www.acmicpc.net/problem/2206
• 분류 : BFS
• 풀이 시간 : 60분

문제 해설

1. NxM 행렬 존재, 이 안에는 이동할 수 있는 공간(0)과 이동할 수 없는 벽(1)이 존재
2. (1, 1) 부터 (N, M)까지 가는 경로 중 최단 경로는?
3. 단, 벽과 마주했을 때 딱 한번 벽 부술 수 있음
4. 이동은 상하좌우로 이동 가능

Solution

풀이 접근 방법

1. 상하좌우로 이동하면서 경로의 최대값 구하기 = BFS
2. 벽을 한번 부술 수 있음 + 이미 벽 한번 부쉈으면 다음번에 벽 마주하면 이동 못함
   1. 이동하는 Player 변수에 broken 값으로 표시
3. 하나의 공간이라도 벽을 부쉈을 때와 부수지 않았을 때의 값이 다를 수 있음
   1. 3차원 배열을 통해 벽을 부쉈을 때 / 벽을 부수지 않았을 때 해당 위치의 방문 여부를 저장

정답 코드

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

public class Main {
  static class Player {
    // x, y 좌표 / 이동 거리
    int x, y, dist;
    // 벽 부숨 여부
    boolean broken;

    public Player() {
      this.x = 0;
      this.y = 0;
      this.dist = 1;
      this.broken = false;
    }

    public Player(int x, int y, int dist, boolean broken) {
      this.x = x;
      this.y = y;
      this.dist = dist;
      this.broken = broken;
    }

  }

  static int N, M;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.valueOf(st.nextToken());
    M = Integer.valueOf(st.nextToken());
    int[][] map = new int[N][M];

    for (int i = 0; i < N; i++) {
      String[] info = br.readLine().split("");

      for (int j = 0; j < M; j++) {
        map[i][j] = info[j].equals("1") ? 1 : 0;
      }
    }

    int minDist = move(map);

    bw.write(minDist + "\n");
    bw.flush();
    bw.close();
  }

  static int move(int[][] map) {
    // [][][0] : 벽 안부셨을 때, [][][1] : 벽 부셨을 때 방문 여부
    boolean[][][] visited = new boolean[N][M][2];
    Queue<Player> queue = new LinkedList<Player>();
    int[] dx = { 0, 0, 1, -1 }, dy = { 1, -1, 0, 0 };

    queue.add(new Player());
    visited[0][0][0] = true;
    visited[0][0][1] = true;

    while (!queue.isEmpty()) {
      Player player = queue.poll();
      int x = player.x;
      int y = player.y;
      int newDist = player.dist + 1;
      int broken = player.broken ? 1 : 0;

      // 목표 지점에 도착했을 경우 탈출
      if (x == N - 1 && y == M - 1) {
        return player.dist;
      }

      for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (!isIn(nx, ny))
          continue;

        // 벽일 경우
        if (map[nx][ny] == 1) {
          // 벽을 한번도 부수지 않고, 아직 방문 전이라면 방문 가능
          if (!player.broken && !visited[nx][ny][1]) {
            visited[nx][ny][1] = true;
            // 벽 부쉈다는 표시로 broken 값 true로 넣음
            queue.add(new Player(nx, ny, newDist, true));
          }
        } else {
          // 벽이 아닐 경우 : 벽을 부쉈을 때 / 벽은 부수지 않았을 때 모두 이동 가능
          // 이미 방문했으면 방문하지 않음
          if (visited[nx][ny][broken])
            continue;

          visited[nx][ny][broken] = true;
          queue.add(new Player(nx, ny, newDist, player.broken));
        }
      }
    }

    return -1;
  }

  static boolean isIn(int x, int y) {
    if (0 <= x && x < N && 0 <= y && y < M) {
      return true;
    }
    return false;
  }
}