코드트리 [자바 java] 최소 경로로 탈출하기

https://www.codetree.ai/missions/2/problems/escape-with-min-distance?utm_source=clipboard&utm_medium=text 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

이전에 풀었던 네방향 탈출하기 문제와 유사하다. 하지만 다른 점이 있다면 도착까지 거쳐온 칸수를 세야한다는 점이다.

 

이 문제는 dfs보다는 bfs로 푸는 것이 좋은데 그 이유는 bfs는 경로를 탐색하다가 가장 빨리 도착점을 발견한 시점이 최소거리이지만, dfs는 도착점을 발견했더라도, 그 경로가 최소인지 알기 위해서는 모든 경우를 다 해봐야한다. 

 

처음에는 큐에다가 -1을 넣어 출발점으로부터 지나온 경로를 구별하도록 하였는데(-1기준으로 왼쪽은 1칸, 오른쪽은 2칸 이런식) 이렇게 하니까 경로가 없는 경우에는 -1이 무한으로 offer되는 것을 볼 수 있었다.

 

그래서 클래스에다가 이제까지 건너온 칸수를 저장할 수 있도록 cnt요소를 추가했다.

 

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

public class Main {
    static class xy{
        int x;
        int y;
        int cnt;

        xy(int x,int y, int cnt){
            this.x = x;
            this.y = y;
            this.cnt = cnt;
        }
    }

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

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] arr = new int[n][m];
        int[][] vis = new int[n][m];

        for(int i =0;i<n;i++){
             st = new StringTokenizer(br.readLine());
            for(int j =0;j<m;j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        Queue<xy> q = new LinkedList<>();

        q.offer(new xy(0,0,0));

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

        int cnt = 0;

        while(q.isEmpty() != true){
            xy now = q.poll();

            if(vis[now.x][now.y] == 1) continue;
            
            vis[now.x][now.y] = 1;

            if(now.x == n-1 && now.y == m-1) {
                System.out.println(now.cnt);
                System.exit(0);
            }

            for(int j =0;j<4;j++){
                if(now.x + dx[j] >= 0 && now.y + dy[j] >= 0 && now.x + dx[j] < n && now.y + dy[j] < m
                && arr[now.x + dx[j]][now.y + dy[j]] == 1 && vis[now.x + dx[j]][now.y + dy[j]] == 0){
                    q.offer(new xy(now.x + dx[j],now.y + dy[j],now.cnt+1));
                }
            }

        }

        System.out.println(-1);

    }
}