[백준 2206] 벽 부수고 이동하기 (Java)

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

2206번: 벽 부수고 이동하기

접근 방법

bfs를 이용해 풀어야하는 문제이지만

1번 벽을 부수고 이동이 가능하다는 특징이 있었다.

벽을 단 한번만 부술 수 있기 때문에 이를 체크하면서 이동해야한다. 벽을 부순 상태를 남겨 이미 부쉈다면 벽을 지나갈 수 없도록 만들어야한다.

 

일반적인 bfs와 다르게 boolean 타입의 2차원 배열을 이용해서 방문을 체크하는 방법은 시간을 초과한다. 대신 3차원 배열을 만들고 3차원 째 배열의 크기를 2로 두어 벽이 부순 상태가 아닌 경우와 벽이 부순 상태의 경우를 나눠서 방문을 체크해야했다.

(이 부분에 대해서는 이유를 찾지 못했다. 학습이 더 필요한 부분이다.)

 

소스 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	// 상,하,좌,우 이동시키기 위한 배열
    private static int[] x = {1, 0, -1, 0};
    private static int[] y = {0, 1, 0, -1};
    
    private static int N;
    private static int M;
    private static int[][] map;
    
    // 방문 여부를 체크
    private static boolean[][][] isVisited;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();
        M = scanner.nextInt();
        map = new int[N + 1][M + 1];
        
        // isVisited[x][y][0] -> 벽이 부숴진 상태가 아닌 경우 방문 여부
        // isVisited[x][y][1] -> 벽이 부숴진 상태인 경우 방문 여부
        isVisited = new boolean[N + 1][M + 1][2];

        scanner.nextLine();
        for (int i = 1; i <= N; i++) {
            String[] input = scanner.nextLine().split("");
            for (int j = 1; j <= M; j++) {
                map[i][j] = Integer.parseInt(input[j - 1]);
            }
        }

        bfs(1, 1);
    }

    private static void bfs(int px, int py) {
        Queue<Point> queue = new LinkedList<>();

        queue.add(new Point(px, py, 1, 0));
        isVisited[px][py][0] = true;
        isVisited[px][py][1] = true;

        while (!queue.isEmpty()) {
            Point point = queue.poll();

            if (point.px == N && point.py == M) {
                System.out.println(point.depth);
                return;
            }

			// 상하좌우 순차적으로 탐색
            for (int i = 0; i < 4; i++) {
                int newX = point.px + x[i];
                int newY = point.py + y[i];

				// 주어진 N*M 사이즈를 벗어나지 않는지
                if (newX > 0 && newX <= N && newY > 0 && newY <= M) {
                	// 방문한 위치가 벽인 경우
                    if (map[newX][newY] == 1) {
                    	// 벽을 부수지 않았는지 && 벽을 부수지 않았은 경우 방문 안했는지
                        if (point.used == 0 && !isVisited[newX][newY][1]) {
                            queue.add(new Point(newX, newY, point.depth + 1, 1));
                            isVisited[newX][newY][1] = true;
                        }
                    } else {
                    	// 방문한 위치가 벽이 아닌경우
                        // 방문한 이력이 없는지
                        if (!isVisited[newX][newY][point.used]) {
                            queue.add(new Point(newX, newY, point.depth + 1, point.used));
                            isVisited[newX][newY][point.used] = true;
                        }
                    }
                }
            }
        }

        System.out.println(-1);
    }

    private static class Point {
        private int px;
        private int py;
        private int depth;
        private int used;

        Point(int x, int y, int depth, int used) {
            this.px = x;
            this.py = y;
            this.depth = depth;
            this.used = used;
        }
    }
}