백준 알고리즘: 2206번 벽 부수고 이동하기

문제 정보

---

 

2206번: 벽 부수고 이동하기

 

 

핵심

---

얼마나 효율적으로 케이스를 분리해서 문제를 풀이하는가.. 가 중요한 것 같다 (모든 문제가 그렇지만)

이 문제는 BFS(너비 우선 탐색)을 활용하여 풀이하는 문제이며 모든 경우의 수를 확인해야 하는 문제가 아니고 최단 거리를 구하는 문제이기 때문에 DFS는 적합하지 않을 것 같다는 판단을 하였다

중간에 막혔던 부분이 있고, 그 부분을 해결해 나갔던 과정과 함께 풀이를 해보도록 하겠다

 

살짝 소개하자면, 벽은 반드시 한 개만 부술 수 있다

벽을 부수고 간다면 해당 위치(현재 위치)에서는 최단 거리가 될 확률이 높다

하지만 이런 경우를 생각해보면 어떨까?

3 6

010000
010111
000110

map[0][1] 의 벽을 부수고 간다면, map[0][2] 위치에 누구보다 빨리 도착할 수 있다

하지만 결국 목적지에 도달하려면 반드시 map[1][5]의 벽을 부수고 가야만 한다

무턱대고 부수고 이동한 visited[0][2]를 true로 만들어 버린다면, 벽을 부수지 않고 돌아왔을 경우에 이미 방문한 위치를 재방문하지 못하기에 답을 찾을 수 없게 된다

 

그렇기에, visited배열을 현재 2차원에서 3차원으로 확장시키고 벽을 부수지 않은 경우인 visited[row][col][0]과 벽을 부순 경우인 visited[row][col][1]로 나누어서 처리한다면,

앞선 test case에서 벽을 부수고 방문한 map[0][2]를 부수지 않고 돌아오더라도 재방문할 수 있게 되므로 정상적으로 답을 도출해낼 수 있을 것이다.

 

 

풀이

---

package solving;

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

class Main {

  static boolean[][][] visited;
  static int[][] plusNumber = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

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

    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    int[][] map = new int[N][M];
    visited = new boolean[N][M][2];
    for (int row = 0; row < N; row++) {
      String[] oneLine = br.readLine().split("");
      for (int col = 0; col < M; col++) {
        map[row][col] = Integer.parseInt(oneLine[col]);
      }
    }
    System.out.println(bfs(map, N, M));
  }

  public static int bfs(int[][] map, int N, int M) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(new Node(0, 0, 1, false));

    while (!queue.isEmpty()) {
      Node current = queue.poll();
      if (current.row == N - 1 && current.col == M - 1) {
        return current.depth;
      }
      for (int[] ints : plusNumber) {
        int nextRow = current.row + ints[0];
        int nextCol = current.col + ints[1];
        // Invariant Set
        if (nextRow < 0 || nextRow >= N || nextCol < 0 || nextCol >= M) {
          continue;
        }

        // 먼저, 두 경우로 나눈다, 지금껏 벽을 깬적이 있는 경우와 없는 경우
        if (current.isBroke) {
          // 있다면? 더이상 벽을 부술 수 없으므로, 벽이 없는 경우와 방문하지 않은 경우만 따라가면 된다
          if (map[nextRow][nextCol] == 0 && !visited[nextRow][nextCol][1]) {
            visited[nextRow][nextCol][1] = true;
            queue.add(new Node(nextRow, nextCol, current.depth + 1, true));
          }
        } else {
          // 없다면? 하나의 벽을 부술 수 있으므로, 벽인 경우와 벽이 아닌 경우로 나누어 준다
          // 일단, 방문하지 않은 곳만 방문할 수 있으므로 먼저 조건을 처리해 준다
          if (!visited[nextRow][nextCol][0]) {
            // 벽이 아닌 경우라면? 방문 처리를 하고, 큐에 집어 넣는다
            if (map[nextRow][nextCol] == 0) {
              queue.add(new Node(nextRow, nextCol, current.depth + 1, false));
              visited[nextRow][nextCol][0] = true;
            } else {
              // 벽인 경우라면, 벽을 하나 부수고 갈 수 있으므로 벽을 부수고 부쉈다고 표시한 후, 부순 벽의 visited배열을 방문 처리 해준다
              queue.add(new Node(nextRow, nextCol, current.depth + 1, true));
              visited[nextRow][nextCol][1] = true;
            }
          }
        }
      }
    }
    return -1;
  }
}

class Node {

  int row;
  int col;
  int depth;
  boolean isBroke;

  Node(int row, int col, int depth, boolean isBroke) {
    this.row = row;
    this.col = col;
    this.depth = depth;
    this.isBroke = isBroke;
  }
}

 

Node 클래스를 구성하고, 현재 위치의 좌표와 이동한 거리, 벽을 부쉈는지 안부쉈는지를 기록할 수 있도록 하였다

큰 경우로 벽을 부순 적이 있는 경우와 없는 경우로 나누고,

벽을 부순 적이 있다면 -> visited[1]에 방문되지 않았으며 벽이 아닌 경우만 방문이 가능하다

벽을 부순 적이 없다면 -> visited[0]에 방문되지 않았으며, 벽을 부수고 이동하거나 벽을 부수지 않고 이동하거나 총 2가지 경우의 방문이 가능하다

 

 

고찰

---

처음보다 BFS 문제를 맞이할 때, 방문 여부를 기록하는 것에는 익숙해 졌다

이 문제의 경우 벽을 부순 경우와 부수지 않은 경우의 방문 여부 기록 배열을 따로따로 작성하지 않으면 풀이가 불가능 했다

그러므로 이러한 부분에서 유연한 사고를 기를 수 있도록 노력해야 겠다고 생각하였다

 

 

Source Code on GitHub

---