Java 백준 14923 미로 탈출

백준 링크

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

14923번: 미로 탈출

---

문제

입력

출력

입출력 예시

---

제출한 코드

import java.io.*;
import java.util.*;

public class Sucess_BFS_14923 {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    //

    static int n, m;
    static int answer = Integer.MAX_VALUE;
    static int[] start = new int[2];
    static int[] end = new int[2];
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int[][] map;
    static boolean[][][] v;

    public static void main(String[] args) throws Exception {
        init();
        run();
    }

    public static void init() throws Exception {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        map = new int[n][m];
        v = new boolean[n][m][2];
        
        // 시작점
        st = new StringTokenizer(br.readLine());
        start[0] = Integer.parseInt(st.nextToken()) - 1;
        start[1] = Integer.parseInt(st.nextToken()) - 1;

        // 도착점
        st = new StringTokenizer(br.readLine());
        end[0] = Integer.parseInt(st.nextToken()) - 1;
        end[1] = Integer.parseInt(st.nextToken()) - 1;
    
        // 맵 정보
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    public static void run() {
        
        // 로직 시작
        bfs();
        
        // 정답 출력
        if (answer == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.print(answer);
        }
    }

    public static void bfs() {
        Deque<int[]> q = new ArrayDeque<>();
        
        // 벽 부수기 횟수가 있는 경우부터 시작
        v[start[0]][start[1]][1] = true;
        q.add(new int[]{start[0], start[1], 1, 0});

        // BFS 시작
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            
            // 저장된 최소 경로보다 큰 경우 불필요한 연산이라 제거 
            if (cur[3] > answer) {
                continue;
            }
            
            // 새롭게 답이 갱신되는 경우
            if (cur[0] == end[0] && cur[1] == end[1]) {
                answer = cur[3];
                break;
            }
            
            // 상하좌우 확인
            for (int i = 0; i < 4; i++) {
                int nx = cur[0] + dx[i];
                int ny = cur[1] + dy[i];

                if (nx < 0 || ny < 0 || nx >= n || ny >= m || v[nx][ny][cur[2]]) continue;
                
                // 이동이 가능한 좌표
                if (map[nx][ny] == 0) {
                    v[nx][ny][cur[2]] = true;
                    q.add(new int[]{nx, ny, cur[2], cur[3] + 1});
                }
                // 이동이 불가능한 좌표
                else {
                    // 벽 부수기가 가능한 경우
                    if (cur[2] == 1) {
                        v[nx][ny][cur[2]] = true;
                        q.add(new int[]{nx, ny, 0, cur[3] + 1});
                    }
                    // 벽 부수기가 불가능한 경우
                    else {
                        continue;
                    }
                }

            }
        }
    }
}

 

방문처리에 조금 더 신경을 써주면 되는 문제였다.

 

1. 다른 그래프 탐색 문제와 동일하게 입력을 입력 받고 시작한다.

2. init()이 끝난 뒤 run()에서 문제에서 요구하는 부분들을 세팅해준다.

( 해당 문제에서는 이동거리는 최소 도달하지 못하는 경우 -1을 출력해야한다. )

3. BFS를 진행하면서 기존 2차원 배열로 데이터를 핸들링 하던 부분을 수정해야한다.

4. 벽 부수기 1회를 사용한지 체크하기 위해서 방문처리용 배열을 2차원이 아닌 3차원으로 진행한다.

5. end 좌표까지 도달한 최소 이동 횟수보다 큰 경우는 continue 하면서 불필요한 연산을 제거한다.