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

2206번 벽 부수고 이동하기

 

1. 문제 분석

---

• 0은 이동할 수 있는 칸, 1은 벽이 있어서 이동할 수 없는 칸입니다.
• (1, 1)에서 시작해서 (N, M)까지 가는데 최단 경로를 구해야 합니다.
• 이동은 상, 하, 좌, 우로 가능하고, 이때 벽(1)을 최소 한번 부수고 지나갈 수 있습니다.
• 문제에서 주어진 사항을 보고, BFS로 접근해야겠다는 생각을 했습니다.
• 방향이 존재하기 때문에 재귀적으로 구현을 했고, 벽을 1번 이상 부순 경우는 더 이상 나아가지 못하도록 막는 방법을 생각했습니다.
• 계속 틀렸다는 말이 나와서 2차원 배열 visited를 이용하여 문제를 변경해서 풀어봤는데, 이때는 시간 초과가 났습니다.

 

 

 

2. 핵심 아이디어

---

• 특정한 지점 (x, y)에 도달하는 데 있어서 벽을 1번 부수고 가는 경우와 벽을 아예 부수지 않고 가는 경우 중에서 벽을 1번 부수고 가는 경우가 더 빠를 수 있습니다.
• 특정 지점 (x, y)까지의 결과는 위와 같지만, 최종 (N, M)까지 도달하는 데 있어서는 벽을 아예 부수지 않고 가는 경우가 더 빠를 수 있습니다.

 

• 위 그림 처럼 파란 지점까지 벽을 한 번 부수고 가면 3번이면 가는데, 벽을 부수지 않고 가면 13번이 걸립니다.
• 하지만 벽을 한번 부수고 3번으로 지나가면 (N, M)에 도달하지 못하고 정답이 될 수 없습니다.
• 파란 지점에 벽을 한번 부순것이 먼저 도달해서 visited[1][3]을 true로 만들었고, 벽을 부수지 않고 지나가는 경우에 같은 vistied를 사용하게 된다면 해당 경우는 도달할 수 있는 경우가 -1이 됩니다.
• 즉, 벽을 부수고 지나가는 경우에 대한 visited와 벽을 부수지 않고 지나가는 경우에 대한 visited를 나눠서 처리해줘야 합니다.
• 이 문제에서 2차원 배열을 2개 만드는 것 보다 visited[][][]를 3차원 배열로 만들어서 visited[row][col][0]은 벽을 부수고 지나가는 경우에 대한 visited로 사용하고, visited[row][col][1]은 벽을 부수지 않고 지나가는 경우에 대한 visited로 사용하면 쉽게 처리할 수 있습니다.

 

 

 

3. 소스코드

---

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

public class Main {
    static int N, M;
    static int[][] map;
    static boolean[][][] visited;
    static int[][] move = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    
    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());
        map = new int[N + 1][M + 1];
        visited = new boolean[N + 1][M + 1][2]; // (벽을 부수고 가는 경우, 벽을 부수지 않고 가는 경우)
        for (int row = 1; row <= N; row++) {
            char[] input = br.readLine().toCharArray();
            for (int col = 1; col <= M; col++) {
                map[row][col] = input[col - 1] - '0';
            }
        }
        int answer = bfs();
        System.out.println(answer);
    }

    public static int bfs() {
        Queue<Node> nodes = new LinkedList<>();
        nodes.add(new Node(1, 1, 1, false));
        visited[1][1][1] = true;

        while (!nodes.isEmpty()) {
            Node curr = nodes.poll();

            if (curr.row == N && curr.col == M) {
                return curr.dist;
            }

            int nextDist = curr.dist + 1;
            for (int[] m : move) {
                int nextRow = curr.row + m[0];
                int nextCol = curr.col + m[1];
                if (!isValid(nextRow, nextCol)) {
                    continue;
                }

                if (map[nextRow][nextCol] == 1) { // 벽인 경우
                    if (!curr.useBreak && !visited[nextRow][nextCol][0]) { // 아직 부순적이 없는 경우
                        nodes.add(new Node(nextRow, nextCol, nextDist, true));
                        visited[nextRow][nextCol][0] = true;
                    }
                } else if (map[nextRow][nextCol] == 0) { // 벽이 아닌 경우
                    if (curr.useBreak && !visited[nextRow][nextCol][0]) { // 벽을 부수고 가는 경우
                        nodes.add(new Node(nextRow, nextCol, nextDist, true));
                        visited[nextRow][nextCol][0] = true;
                    } else if (!curr.useBreak && !visited[nextRow][nextCol][1]) { // 벽을 부수지 않고 가는 경우
                        nodes.add(new Node(nextRow, nextCol, nextDist, false));
                        visited[nextRow][nextCol][1] = true;
                    }
                }
            }
        }
        return -1;
    }

    public static boolean isValid(int row, int col) {
        return row >= 1 && col >= 1 && row <= N && col <= M;
    }

    static class Node {
        int row, col, dist;
        boolean useBreak;

        public Node (int row, int col, int dist, boolean useBreak) {
            this.row = row;
            this.col = col;
            this.dist = dist;
            this.useBreak = useBreak;
        }
    }
}

 

위 코드에서 핵심적인 부분은 다음과 같습니다.

if (map[nextRow][nextCol] == 1) {
    if (!curr.useBreak && !visited[nextRow][nextCol][0]) {
        nodes.add(new Node(nextRow, nextCol, nextDist, true));
        visited[nextRow][nextCol][0] = true;
    }
} else if (map[nextRow][nextCol] == 0) {
    if (curr.useBreak && !visited[nextRow][nextCol][0]) {
        nodes.add(new Node(nextRow, nextCol, nextDist, true));
        visited[nextRow][nextCol][0] = true;
    } else if (!curr.useBreak && !visited[nextRow][nextCol][1]) {
        nodes.add(new Node(nextRow, nextCol, nextDist, false));
        visited[nextRow][nextCol][1] = true;
    }
}

• 만약 다음에 내가 가야할 곳이 벽(1)이라면
  
  
  1. 내가 Break를 사용했는지 판단합니다. (curr.useBreak가 false인지 확인)
  2. 벽을 부수고 지나가는 경우(visited[][][0])에 이미 방문된 칸인지 확인합니다.
  3. Break을 이미 사용한 경우에 벽(1)을 만나면 Queue에는 아무런 노드도 넣지 않습니다. (이미 끝)
     
     
• 만약 다음에 내가 가야할 곳이 벽이 아니라면(0)
  
  
  1. 내가 Break를 사용했는지 판단합니다.
  2. 만약 이미 Break를 사용했다면 visited[][][0]의 방문처리 상태를 확인합니다.
  3. 아직 Break를 사용하지 않았다면 visited[][][1]의 방문처리 상태를 확인합니다.

이렇게 문제에 접근해볼 수 있습니다. 사실 핵심 아이디어만 떠올렸다면 절대 어렵지 않은 문제였던 거 같습니다. 벽을 부술 수 있는 횟수가 정해져 있기 때문에 이런 식으로 접근해 볼 수 있을 거 같습니다.

 

visited를 3차원 배열로...메..모...