문제

벽부수고 이동하기(Gold 4) - 2206

---

문제 이해

• (1,1)부터 (N,M)까지 이동할때의 최단 경로 구하기
• 한개의 벽까지만 부술 수 있다
• 상,하,좌,우로 이동 가능

---

코드

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

/* baekjoon 2206 */

public class Move {
  public static class Location {
    int r;
    int c;
    int distance; // 현재까지 이동한 거리
    boolean isCrash; // 벽을 부쉈는지 확인

    public Location(int r, int c, int distance, boolean isCrash) {
      this.r = r;
      this.c = c;
      this.distance = distance;
      this.isCrash = isCrash;
    }
  }

  static int N;
  static int M;
  static int[][] map;
  static boolean[][][] visited; // 벽을 부순 경우와 벽을 부수지 않은 경우의 방문 여부 확인
  static int[][] canMove = {
      { -1, 0 },
      { 1, 0 },
      { 0, -1 },
      { 0, 1 },
  };
  static Queue<Location> queue;

  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());
    queue = new LinkedList<>();
    map = new int[N][M];
    visited = new boolean[N][M][2];

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      String[] mapElements = st.nextToken().split("");
      for (int j = 0; j < M; j++)
        map[i][j] = Integer.parseInt(mapElements[j]);
    }

    bfs(0, 0, false);
  }

  public static void bfs(int r, int c, boolean isCrash) {
    queue.add(new Location(r, c, 1, isCrash));
    visited[r][c][0] = true;

    while (!queue.isEmpty()) {
      Location current = queue.poll();
	  
      // 현재 위치가 (N, M) 이면 종료
      if (current.r == N - 1 && current.c == M - 1) {
        System.out.println(current.distance);
        return;
      }

      for (int i = 0; i < canMove.length; i++) {
        int nextR = current.r + canMove[i][0];
        int nextC = current.c + canMove[i][1];

        if ((0 <= nextR && nextR < N) && (0 <= nextC && nextC < M)) {
          if (map[nextR][nextC] == 0) { // 벽이 아니면
            if (current.isCrash && !visited[nextR][nextC][1]) { // 벽을 부순적이 있으면
              visited[nextR][nextC][1] = true;
              queue.add(new Location(nextR, nextC, current.distance + 1, current.isCrash));
            } else if (!current.isCrash && !visited[nextR][nextC][0]) { // 부순 적이 없으면
              visited[nextR][nextC][0] = true;
              queue.add(new Location(nextR, nextC, current.distance + 1, current.isCrash));
            }
          } else { // 벽이면
            if (!current.isCrash) { // 벽을 부순다
              visited[nextR][nextC][1] = true;
              queue.add(new Location(nextR, nextC, current.distance + 1, true));
            }
          }
        }
      }
    }
    // 이동 못할 경우
    System.out.println("-1");
  }
}

---

코드 설명

• 여태 풀었던 문제들과 달랐던 점 : 방문 여부를 3차원 배열로 사용

1. N, M을 입력받고 map을 입력받는다.
2. 방문했는지 확인하기 위한 visted배열을 선언한다.
3. 최단거리이기 때문에 bfs() 함수를 이용한다.
   4-1. 현재 위치를 queue에 넣고 현재 위치를 방문했다고 표시한다. 이때 아직 벽을 부수지 않았을 때의 방문 여부에 반영한다.
   4-2. 현재 위치가 (N, M)이면 결과를 출력하고 종료한다.
   4-3. 상,하,좌,우를 탐색한다.
   4-4. 벽이 아니고 한번도 벽을 부순적이 있다면 벽을 부순 방문여부에 다음 위치를 방문했다고 표시, 벽이 아니고 벽을 부순적이 없다면 벽을 부수지 않은 방문여부에 위치를 표시
   4-5. 벽이고 방문하면서 한번도 벽을 부수지 않았다면 벽을 부순 방문여부에 다음위치를 방문했다고 표시

visited 배열을 3차원으로 구현할 생각이 나지 않아 오랫동안 고민을 했다. 여러 형태에 대해서 좀 더 열린 생각을 할 수 있도록 하자!

---