[백준 알고리즘] 2206번 벽 부수고 이동하기(Java) 문제 풀이

문제

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

2206번: 벽 부수고 이동하기

문제에 대한 이해

벽을 최대 1개까지 부술수 있으며, 0,0 ~ N-1, M-1까지 가야하는 탐색 문제이다.

어떻게 풀 것인가?

최근에 공부했던 0-1BFS를 응용하여 문제를 접근했다. 다만 응용기법이 잘 못되었는지 계속 틀려서 어쩔수 없이 아랫분의 블로그를 참고했다.

https://iseunghan.tistory.com/316

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

윗분은 거리를 계산하는 부분에서 배열을 사용하셨는데, 이 과정에서 아무래도 오류가나서 틀렸던 것 같다. 그래서 윗분의 풀이를 참고하여 응용하였다.

풀면서 놓쳤던점

거리 계산에서 많이 틀렸다.

이 문제를 통해 얻어갈 것

BFS에 대한 응용

내 코드 

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

// 백준알고리즘 2206번 벽 부수고 이동하기
public class Main {
    static int N, M;
    static int[][] arr;

    static int[][] dist;    // 거리 측정 배열
    static boolean[][][] visit;    // 벽을 부순 여부에 따라 방문 여부 기록

    public static int[] dx = {-1, 0, 1, 0};

    public static int[] dy = {0, 1, 0, -1};
    static int result = -1;

    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());
        arr = new int[N][M];
        dist = new int[N][M];
        visit = new boolean[2][N][M];

        // 시작지점과 도착지점이 같을 경우!
        if (N - 1 == 0 && M - 1 == 0) {
            System.out.print(1);
            System.exit(0);
        }

        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            for (int j = 0; j < M; j++) {
                arr[i][j] = str.charAt(j) - '0';
            }
        }
        BFS();
        System.out.println(result);

    }

    private static void BFS() {
        LinkedList<int[]> que = new LinkedList<>();
        que.offer(new int[]{0, 0, 0});
        arr[0][0] = -1;

        while (!que.isEmpty()) {
            int[] poll = que.poll();
            int x = poll[0];
            int y = poll[1];
            int z = poll[2]; // 지나온 경로 세기

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

                if (nowX < 0 || nowY < 0 || N <= nowX || M <= nowY) {
                    continue;
                }

                if (arr[nowX][nowY] == 1) {
                    if (z == 0 && !visit[1][nowX][nowY]) {
                        visit[z][nowX][nowY] = true;    // 방문 처리
                        dist[nowX][nowY] = dist[x][y] + 1; // 거리 측정
                        que.offer(new int[]{nowX, nowY, 1});
                    }
                } else {
                    if (!visit[z][nowX][nowY]) {
                        // 해당 칸을 방문을 안했을 때!
                        visit[z][nowX][nowY] = true;    // 방문 처리
                        dist[nowX][nowY] = dist[x][y] + 1; // 거리 측정
                        que.offer(new int[]{nowX, nowY, z}); // 다시 큐에 넣어줘서 BFS!
                    }
                }

                if (nowX == N - 1 && nowY == M - 1) {
                    result = dist[nowX][nowY] + 1;
                    return;
                }
            }
        }
    }
}