[BOJ] 2206 - 벽 부수고 이동하기 JAVA

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

예제 입력 1

6 4

0100

1110

1000

0000

0111

0000

예제 출력 1

15

예제 입력 2

4 4

0111

1111

1111

1110

예제 출력 2

-1

 

 

 

 

 

 

풀이 1. (틀린 코드)

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

class Pair {
    int r, c;
    Pair(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[][] map = null;
    static int[][][] path = null;
    static int N, M;
    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1, 1};

    public static void bfs() {
        Queue<Pair> que = new ArrayDeque<>();
        que.add(new Pair(0, 0));
        path[0][0][0] = 1;

        while(!que.isEmpty()) {
            Pair p = que.poll();
            int r = p.r;
            int c = p.c;

            for(int i = 0; i < 4; i++) {
                int nr = r + rArr[i];
                int nc = c + cArr[i];

                if(-1 < nr && nr < N && -1 < nc && nc < M) {
                    // 다음 좌표가 0일 때는 이전에 벽을 부쉈든 안 부쉈든 이동 가능
                    // 1. 이전에 벽을 부순 적 없고 이번에도 안 부수고 이동
                    // 2. 이전에 벽을 부순 적 있고 이번에는 안 부수고 이동

                    // 1. 이전에 벽을 부순 적 없고 이번에도 안 부수고 이동
                    if(map[nr][nc] == 0  // 벽 안 부수고 갈 수 있니?
                            && path[nr][nc][0] == N * M  // 벽 안 부수고 방문 안 했던 노드 맞니?
                            && path[r][c][1] == N * M) {  // 지금까지 벽 부순 적 없는 거 맞니?
                        path[nr][nc][0] = path[r][c][0] + 1;
                        que.add(new Pair(nr, nc));
                    }
                    // 2. 이전에 벽을 부순 적 있고 이번에는 안 부수고 이동
                    if(map[nr][nc] == 0  // 벽 안 부수고 갈 수 있니?
                            && path[nr][nc][1] == N * M  // 벽 부수고 방문 안 했던 노드 맞니?
                            && path[r][c][1] != N * M) {  // 지금까지 벽 부순 적 있는 거 맞니?
                        path[nr][nc][1] = path[r][c][1] + 1;
                        que.add(new Pair(nr, nc));
                    }

                    // 다음 좌표가 1일 때는 이전에 벽을 안 부쉈을 경우만 이동 가능
                    // 3. 이전에 벽을 안 부쉈고 이번에 부수면서 이동
                    if(map[nr][nc] == 1  // 벽 부숴야 갈 수 있는 거 맞니?
                            && path[nr][nc][1] == N * M  // 이전에 벽 부수고 방문한 적 없는 거 맞니?
                            && path[r][c][1] == N * M) {  // 지금까지 벽 부순 적 없는 거 맞니?
                        path[nr][nc][1] = path[r][c][0] + 1;  // 이번 턴에서 벽을 부숨
                        que.add(new Pair(nr, nc));
                    }
                }

            }
        }
    }

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

        map = new int[N][M];
        path = new int[N][M][2];
        for(int i = 0; i < N; i++) {
            String str = br.readLine();
            for(int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
                Arrays.fill(path[i][j], N * M);
            }
        }

        bfs();
        int ans = 0;
        if(path[N-1][M-1][0] == N*M && path[N-1][M-1][1] == N*M) {  // 이동할 수 없는 경우
            ans = -1;
        }else if(path[N-1][M-1][0] < path[N-1][M-1][1]) {
            ans = path[N-1][M-1][0];
        }else {
            ans = path[N-1][M-1][1];
        }
        System.out.println(ans);
    }
}

 

path[r][c][0] = (r, c)에 벽을 한 번도 부수지 않고 이동하는 최단경로

path[r][c][1] = (r, c)에 벽을 한 번만 부수고 이동하는 최단경로

 

이렇게 잡아두고 모든 경로를 계산하려 했다.

 

주어진 예제들에 대해서는 맞게 동작하는데 11%에서 틀려버린다.. 

어디가 틀린 건지 모르겠다.

 

세 가지 경우의 수에 대해서 쓸 데 없는 조건도 하나씩 들어가있는 거 같아서 제거해보았지만 여전히 틀린다.

 

 

 

 

 

풀이 2. (정답 코드)

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

class Pair {
    int r, c, cnt, destroy;
    Pair(int r, int c, int cnt, int destroy) {
        this.r = r;
        this.c = c;
        this.cnt = cnt;
        this.destroy = destroy;
    }
}

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[][] map = null;
    static boolean[][][] check = null;
    static int N, M, ans = -1;
    static int[] rArr = {-1, 1, 0, 0};
    static int[] cArr = {0, 0, -1, 1};

    public static void bfs() {
        Queue<Pair> que = new ArrayDeque<>();
        que.add(new Pair(0, 0, 1, 0));
        check[0][0][0] = true;

        while(!que.isEmpty()) {
            Pair p = que.poll();
            int r = p.r;
            int c = p.c;
            int cnt = p.cnt;
            int destroy = p.destroy;

            if(r == N - 1 && c == M - 1) {
                ans = cnt;
                return;
            }

            for(int i = 0; i < 4; i++) {
                int nr = r + rArr[i];
                int nc = c + cArr[i];

                if(-1 < nr && nr < N && -1 < nc && nc < M) {
                    if(map[nr][nc] == 1) {  // 벽이면??
                        if(destroy == 0 && !check[nr][nc][1]) {  // 이전에 부순적 없으면 부수고 이동
                            que.add(new Pair(nr, nc, cnt + 1,  destroy + 1));
                            check[nr][nc][destroy+1] = true;
                        }
                    }else{  // 벽이 아니면??
                        if(!check[nr][nc][destroy]) {  // 현재 destroy 횟수로 다음 좌표 갈 수 있는지만
                            que.add(new Pair(nr, nc, cnt + 1, destroy));  // destroy 유지하면서 이동
                            check[nr][nc][destroy] = true;
                        }
                    }
                }
            }
        }
    }

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

        map = new int[N][M];
        check = new boolean[N][M][2];
        for(int i = 0; i < N; i++) {
            String str = br.readLine();
            for(int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j) - '0';
            }
        }
        bfs();
        System.out.println(ans);
    }
}

 

check와 cnt를 하나의 배열로 관리하고 싶어서 path[][][]를 사용했던 건데 오히려 그것 때문에 더 헷갈리게 된 거 같다. 코드도 지저분했고.

 

Pair 안에 cnt와 destroy(지금까지 벽 부순 횟수)를 포함하도록 짰더니 훨씬 깔끔해졌다.