백준 2206번: 벽 부수고 이동하기 (JAVA)

https://www.acmicpc.net/problem/2206

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

 

---

 

풀이

(i, j) 위치에 대해, 벽을 부수지 않고 가장 빨리 도착하는 이동 수, 벽을 한 번 부수고 가장 빨리 도착하는 이동 수를 기록하는 int[][] 2개를 선언한다. 이를 각각 dist1, dist2라고 하자. 이후, queue에 {row, col, 부쉈는가?}를 기록한 int[]을 넣어서 bfs를 돌린다. 처음에는 당연히 {0, 0, 안 부쉈다}을 넣으면 된다. 

bfs 과정 내, (r,c)에서 (nr, nc)로 간다고 할 때,

1) 안 부쉈는데 벽을 지나가려고 하는 경우: dist2[nr][nc]에 dist1[r][c] + 1을 넣고, queue에 {nr, nc, 부쉈다}를 넣는다.

2) 안 부쉈는데 땅을 지나가려는 하는 경우: dist1에 거리 기록, 일반적인 bfs처럼 진행한다.

3) 벽을 부쉈는데 벽을 지나가려고 하는 경우: 안 된다

4) 벽을 부쉈는데 땅을 지나가려고 하는 경우: dist2에 거리 기록, bfs

 

배울 점

dist1, dist2로 나누지 않고 bfs에 넣는 원소에만 부쉈는지에 대한 값을 주려고 했는데, 이러면 안 되는 경우가

5 5

00000

11110

00000

11111

00000

이 있다.

bfs 기본이면 기본적으로 주어지는 공간에서 숫자만 잘 가지고 놀면 처리가 되는데, 조금 응용이다 싶으면 다른 상태, 조건 등을 기록하는 배열 (dist, visited 등)을 만들어서 관리해주자.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Collection;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // M, N 바꿔썼음
        int M = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());

        int[] dr = {-1, 1, 0, 0};
        int[] dc = {0, 0, -1, 1};
        int[][] map = new int[M][N];
        int[][] dist1 = new int[M][N];
        int[][] dist2 = new int[M][N];
        dist1[0][0] = 1;
        dist2[0][0] = 1;


        for (int i = 0; i < M; i++) {
            String str = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }

        Queue<int[]> queue = new ArrayDeque<>(); // {row, col, 벽부셨는지 0 or 1로}
        queue.offer(new int[] {0, 0, 0});
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            int row = temp[0];
            int col = temp[1];
            int broken = temp[2];
            for (int i = 0; i < 4; i++) {
                int nr = row + dr[i];
                int nc = col + dc[i];
                if (nr < 0 || nr >= M || nc < 0 || nc >= N) continue;
                if (broken == 0) {
                    if (map[nr][nc] == 1 && (dist2[nr][nc] == 0 || dist2[nr][nc] > dist1[row][col] + 1)) {
                        dist2[nr][nc] = dist1[row][col] + 1;
                        queue.offer(new int[] {nr, nc, 1});
                    }
                    else if (map[nr][nc] == 0 && (dist1[nr][nc] == 0 || dist1[nr][nc] > dist1[row][col] + 1)) {
                        dist1[nr][nc] = dist1[row][col] + 1;
                        queue.offer(new int[] {nr, nc, broken});
                    }
                }
                else {
                    if (map[nr][nc] == 0 && (dist2[nr][nc] == 0 || dist2[nr][nc] > dist2[row][col] + 1)) {
                        dist2[nr][nc] = dist2[row][col] + 1;
                        queue.offer(new int[] {nr, nc, broken});
                    }
                }
            }
        }
		
        // 확인하는 과정: 쓸데없이 긴데 어려운 건 아니다.
        if (dist1[M-1][N-1] == 0) {
            if (dist2[M-1][N-1] == 0) {
                System.out.println(-1);
            }
            else {
                System.out.println(dist2[M-1][N-1]);
            }
        }
        else {
            if (dist2[M-1][N-1] == 0) {
                System.out.println(dist1[M-1][N-1]);
            }
            else {
                System.out.println(Math.min(dist1[M-1][N-1], dist2[M-1][N-1]));

            }
        }


    }

}

 

 P.S.

'부셨다'가 아니라 '부쉈다'구나...