[JAVA 알고리즘]BAEKJOON 2206번 벽 부수고 이동하기

벽 부수고 이동하기

---

문제 설명

N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

출력

첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

제한사항

• 없음

입출력 예

input	return
6 4 0100 1110 1000 0000 0111 0000	15
4 4 0111 1111 1111 1110	-1
추가 반례
6 4 0000 1110 1000 0000 0111 0000	9

---

문제 분석

최단 경로를 구하기 위해서 너비 탐색을 이용한다.

• 움직이는 방향은 상하좌우 4방향에 있는 인접한 0일 때 경로를 움직이고 1일 때는 움직이지 못한다.
• 단, 1일 때 한 번만 부수고 이동할 수 있기 때문에 확인해주는 게 필요하다.
• 벽을 뚫고 지나간 경우와 벽을 뚫고 지나가지 않은 경우를 따로 표시해 경로를 이동할 수 있게 해 준다.

도착지에 도착하지 못한다면 -1을 출력하고 아니면 움직인 거리를 출력한다.

손으로 풀기

1. 입력 크기로 배열의 크기를 정하고 나머지 입력값으로 배열에 넣어준다.
2. 좌표와 그냥 이동과 벽을 부수고 이동하는 것을 구분하여 이동을 표시하기 위해 3차원 배열을 이용한다.
3. 큐를 이용해서 좌표와 이동 횟수, 벽 이동 유무를 체크해 4방향 이동한다.
4. 일반적으로 길을 지날 때와 벽을 부수고 지날 때를 구분해서 이동한다.

나의 문제풀이

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

public class Main {
    
    static char[][] map;
    static boolean[][][] visited;
    static int N, M;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(stringTokenizer.nextToken());
        M = Integer.parseInt(stringTokenizer.nextToken());

        // 간단하게 표시하기위해 char로 배열 선언
        map = new char[N][M];
        visited = new boolean[N][M][2];
        for (int i = 0; i < N; i++) {
            map[i] = bufferedReader.readLine().toCharArray();
        }

        // 최단 거리 출력
        System.out.println(bfs());
    }

    private static int bfs() {
        int[] dx = {1, -1, 0, 0};
        int[] dy = {0, 0, 1, -1};

        Queue<int[]> queue = new LinkedList<>();
        visited[0][0][0] = true;
        queue.offer(new int[]{0, 0, 1, 0});
        while (!queue.isEmpty()) {
            int[] coordinate = queue.poll();
            int x = coordinate[0];
            int y = coordinate[1];
            int cnt = coordinate[2];
            int check = coordinate[3];

            // 도착지에서 거리 출력
            if (x == N-1 && y == M-1) {
                return cnt;
            }

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

                if (nextX >= 0 && nextY >= 0 && nextX < N && nextY < M && !visited[nextX][nextY][check]) {
                    // 일반적으로 길 지나가기
                    if (map[nextX][nextY] == '0') {
                        visited[nextX][nextY][check] = true;
                        queue.offer(new int[]{nextX, nextY, cnt + 1, check});
                    }
                    // 벽은 한번만 부실수 있다.
                    if (check == 0 && map[nextX][nextY] == '1') {
                        visited[nextX][nextY][1] = true;
                        queue.offer(new int[]{nextX, nextY, cnt + 1, 1});
                    }
                }
            }
        }
        return -1;
    }
}

처음에는 클래스를 이용해서 큐에 넣고 좌표이동을 하면서, boolean타입으로 벽을 이동 유무를 표시해서 사용을 했는데, 벽을 부수고 지나온 경우와 그냥 이동한 경우가 겹쳤을 경우, 막힌 곳에서 벽을 부수고 지나온 경우는 벽을 부시지 못하고 이동을 체크해 버리고 그냥 이동한 경우는 벽을 부시고 지나갈 수 있지만, 이미 이동을 했다고 표시했기 때문에 이동을 못해 최단 경로로 나오지 않는 문제가 발생했다. 
해당 문제를 해결하기 위해서 벽을 부신경우와 안 부신경우를 따로 이동 유무를 표시하는 것으로 변경을 하고 배열에 넣어서 사용하기에는 boolean타입보다 그냥 int로 사용하는 편이 사용하기 편하기 때문에 클래스를 사용하지 않고 배열을 이용해서 큐를 반복하도록 변경을 하였다.

---

알고리즘 분류

• 그래프 이론
• 그래프 탐색
• 너비 우선 탐색

문제 출처 - https://www.acmicpc.net/problem/2206