[백준] 14923번 탈출 - Java, 자바

14923번 탈출

난이도

실버 3

문제 설명

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

요구사항

• N*M 격자
• 시작 (Hx, Hy) 도착(Ex, Ey)
• 0 = 빈칸, 1 = 벽
• 도달 가능하다면, 도달까지의 최단 거리를 출력하고 그렇지않다면 -1을 출력.
• 마법 지팡이를 사용하여 벽을 1회 부술 수 있다(벽을 부수는데 시간은 0).

접근 방식

미로를 탈출할 수 있는 최단 경로를 구하는 문제이기 때문에 BFS 탐색으로 이용하여 문제를 풀어야 된다고 생각했고 복잡도를 고려하여 BFS를 적용하여야 한다고 생각했다.
가장 중요한 점으로, 벽을 1회 부술 수 있기 때문에 방문한 칸에 대해 체크하는 작업을 마법을 사용했을 때와 사용하지 않았을 때로 구분하여야 된다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

class Point{
    int x;
    int y;
    int time;
    int magic;

    public Point(int x, int y, int time, int magic) {
        this.x = x;
        this.y = y;
        this.time = time;
        this.magic = magic;
    }
}

public class Main{
    static int n, m, Hx, Hy, Ex, Ey, answer=Integer.MAX_VALUE;
    static int[][] arr;
    static int[][][] visited;
    static int[] dx = {0, -1, 0, 1};
    static int[] dy = {-1, 0, 1, 0};
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Hx  = Integer.parseInt(st.nextToken());
        Hy = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        Ex = Integer.parseInt(st.nextToken());
        Ey = Integer.parseInt(st.nextToken());
        arr = new int[n+1][m+1];
        visited = new int[n+1][m+1][2];

        for(int i=1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=m; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        BFS();
        if(answer == Integer.MAX_VALUE) System.out.println(-1);
        else System.out.println(answer);
    }

    static void BFS(){
        Queue<Point> q = new LinkedList<>();
        visited[Hx][Hy][0] = 1;
        q.offer(new Point(Hx, Hy, 0, 0));
        while (!q.isEmpty()){
            Point now = q.poll();
            if(now.x == Ex && now.y == Ey) answer = Math.min(answer, now.time);
            for(int i=0; i<4; i++){
                int nx = now.x + dx[i];
                int ny = now.y + dy[i];
                if(nx>=1 && nx<=n && ny>=1 && ny <=m){
                    // 다음 칸이 빈 칸일 때
                    if(arr[nx][ny] == 0){
                        if(visited[nx][ny][now.magic] == 0){
                            visited[nx][ny][now.magic] = 1;
                            q.offer(new Point(nx, ny, now.time+1, now.magic));
                        }
                    }
                    // 다음 칸이 벽일 때
                    else{
                        // 마법 지팡이를 1회 사용할 때
                        if(visited[nx][ny][1] == 0 && now.magic==0){
                            visited[nx][ny][1] = 1;
                            q.offer(new Point(nx, ny, now.time+1, 1));
                        }
                    }

                }
            }
        }
    }
}

복잡도 분석

각 상태에서 인접한 4방향 -> 시간 O(NM)

느낀점

쉽게 풀 수 있는 문제라고 생각하였지만, 생각보다 시간이 오래 걸린 문제였다. 그 이유는 방문한 칸을 체크하는 배열을 마법을 사용했을 때와 마법을 사용하지 않았을 때로 구분하지 않아 문제를 해결할 수 없었다.
체크 배열을 구분하지 않는다면, 조금 돌아갔지만 지팡이 사용을 아껴 이후에 필요한 벽을 부수고 도착하는 경우가 생략되기 때문이였다.
이 문제를 통해, 체크 배열을 3차원으로 선언하여 BFS로 탐색하면 한 번에 O(NM)으로 문제를 해결할 수 있고 "벽 1회 부수기"류 문제의 대한 정석 패턴 감각을 키울 수 있었다.