벽 부수고 이동하기

문제 설명

• 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을 출력한다.

예제 입력 1

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1

15

예제 입력 2

4 4
0111
1111
1111
1110

예제 출력 2

-1

풀이

접근법은 다음과 같다.

1. 입력을 받아올 board 2차원 배열을 선언한다. 이때, (0, 0)부터 시작하므로 크기는 n, m만큼 선언한다.
2. 이때, 최단 경로(= bfs)를 구하기 위해 방문 여부를 담아줄 visited 2차원 배열을 선언한다.
3. 한 행을 받아온 후, - '0'을 함으로써 '0' 또는 '1'로 변환하여 board에 값을 저장한다.
4. bfs를 수행하기 위한 메서드를 선언한다.
5. (중요) 큐를 선언한다. 이때, 큐에는 z(= 벽을 부순 적이 있는지 없는지의 여부), x(= 행), y(= 열)이 삽입되므로 int형 배열을 담을 수 있도록 선언한다.
6. 원점에서 출발하므로 [0, 0, 0]을 큐에 담는다.
7. 큐가 비어있을 때까지, 즉 모든 경로를 다 탐색할 때까지 반복하기 위한 while문을 선언한다.
8. 큐에 담긴 배열에서 z, x, y는 각각 분리하여 좌표로써 사용하기 위해 변수로 사용한다.
9. (접근법을 어떻게 구현할지 알고 있다는 가정 하에) 상/하/좌/우로 탐색하기 전에 좌표값과 n, m이 같아졌을 때(= 단, 원점에서부터 출발했으므로 n, m에서 -1을 수행) 탈출하기 위한 조건을 미리 지정하여 리턴한다. (= return visited[z][x][y];)
10. 4방향(= 상/하/좌/우)로 탐색하기 위한 for문을 선언한다.
11. n x m 크기의 맵을 벗어날 경우, 올바른 경로가 아니므로 다음 반복으로 넘어가기 위한 continue를 작성한다.
12. 가고자 하는 좌표의 값이 0인지 1인지에 따라 벽을 부술지 말지를 나눠서 작성한다.
13. 이때 벽은 단 한 번만 부술 수 있으므로, 벽을 부순 적이 있는지 / 없는지를 if-else가 아닌 if-if 로 작성한다.
14. 벽을 마주했으나 벽을 부순 적이 없다면(= board[nx][ny] == 1 && z == 0) 벽을 부수면 되므로 visited의 z 값을 1로 업데이트한 후, 큐에도 1을 넣는다(= visited[1][nx][ny] = visited[0][x][y] + 1; queue.offer(new int[]{1, nx, ny});)
15. 이때, 해당 메서드의 반환 타입은 int + 최단 경로를 구할 수 없는 상황이라면 while문을 수행하지 않았을 것이므로 -1을 반환한다.

고민했던 포인트들

1. board의 크기는 [n][m]과 [n + 1][m + 1] 중 어떻게 설정해야할까?
2. board[i][j] = Integer.valueOf(row.charAt(j) - '0'); 과 달리 board[i][j] = Integer.parseInt(row.charAt(j) - '0');는 왜 수행할 수 없을까?
3. bfs의 반환 타입을 void vs int 중 어떻게 처리해야할까?
4. 큐에는 어떤 자료형 타입과 함께 구조가 들어가야할까?
5. 탐색의 기준을 어떻게 나눠야할까?
6. 벽을 부순 적 없음을 어떻게 나타내야할까?
7. 벽을 마주했으나(= 1을 마주했으나) 벽을 부수려하는 경우는 고려해야할까?
8. while문의 종료 조건은 어떻게 설정해줘야할까? 즉, (n, m)을 마주했을 경우 (n, m)이 아닌 (n - 1, m - 1)로 설정해줘야 할까?

전체 코드

package silver.class4;

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

public class BreakingWall {
    private static int n, m;
    private static int[] dx = {-1, 1, 0, 0}; // 상하좌우
    private static int[] dy = {0, 0, -1, 1};
    private static int[][] board;
    private static int[][][] visited;

    //    private static int result;
    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());
        board = new int[n][m];

        for (int i = 0; i < n; i++) {
            String row = br.readLine();
            for (int j = 0; j < m; j++) {
                board[i][j] = Integer.valueOf(row.charAt(j) - '0');
            }
        }

        // Todo 벽이라면 -> 벽을 부순 적 없다면 -> 부수고 이동 / 부순 적 있다면 -> 안 부수고 이동
        // Todo 벽이 아니라면 -> 이동
        System.out.println(bfs());
        br.close();
    }

    private static int bfs() {
        visited = new int[2][n][m]; // Todo visited : 최단 거리의 값

        Queue<int[]> queue = new LinkedList<>(); // Todo 큐 : 방문할 인접 노드
        queue.offer(new int[]{0, 0, 0});
        visited[0][0][0] = 1;

        while (!queue.isEmpty()) {
            int[] node = queue.poll();
            int z = node[0];
            int x = node[1];
            int y = node[2];

            // Todo 즉, 탈출 조건을 미리 알려주는게 무한 루프가 아닌지를 판단할 겸 + 가독성을 위해서 현 시점에 선언
            // Todo 단, 구조를 다 알고 해당 메서드(= bfs())를 설계할 때 미리 선언할 수 있음
            if (x == n - 1 && y == m - 1) {
                return visited[z][x][y];
            }

            int distance = 4;
            for (int i = 0; i < distance; i++) {
                int nx = x + dx[i]; // 상하
                int ny = y + dy[i]; // 좌우

                if (nx >= n || ny >= m || nx < 0 || ny < 0) {
                    continue;
                }

                if (board[nx][ny] == 0 && visited[z][nx][ny] == 0) {
                    visited[z][nx][ny] = visited[z][x][y] + 1;
                    queue.offer(new int[]{z, nx, ny});
                    continue;
                }
                if (board[nx][ny] == 1 && z == 0) {
                    visited[1][nx][ny] = visited[0][x][y] + 1;
                    queue.offer(new int[]{1, nx, ny});
                }
            }
        }


        return -1;
    }
}

후기

약 1~2달 전에 풀었던 문제인데, 그때는 몰랐어서 별다른 고민 없이 답을 봤었다.

그리고 다시 풀게 되었으나.. 대략적인 접근법은 기억이 났지만 어떻게 구현해야할지를 모르겠어서 상당히 갈팡질팡했던 문제다.

또, 오랜만에 bfs / dfs와 같은 그래프 탐색을 풀어서 그런지 구조가 살짝 어색해서 일일히 주석으로 남겨놓기도 했다.

역시 코테 문제는 끊임없이 풀어야 함을 다시 한 번 느껴버린 문제! (feat. 도와주신 코테 스터디원 분 감사합니다.)