[Algo] 프로그래머스 게임 맵 최단거리

코드

import java.util.*;

class Solution {
    static class Node{
        int r,c, cnt;
        Node(int r, int c, int cnt){
            this.r=r;
            this.c=c;
            this.cnt=cnt;
        }
        
    }
    static int [][]vector={{0,1},{1,0},{0,-1},{-1,0}};
    public int solution(int[][] maps) {
        int answer = -1;
        int n=maps.length;
        int m=maps[0].length;
        boolean [][]check=new boolean[n][m];
        Queue<Node>q=new LinkedList<>();
        q.add(new Node(0,0,1));
        while(!q.isEmpty()){
            Node now=q.poll();
            if(now.r==n-1&&now.c==m-1){
                answer=now.cnt;
                break;
            }
            
            for(int k=0; k<4; k++){
                int x=now.r+vector[k][0];
                int y=now.c+vector[k][1];
                if(x>=0&&y>=0&&x<n&&y<m&&maps[x][y]==1&&!check[x][y]){
                    q.add(new Node(x,y,now.cnt+1));
                    check[x][y]=true;
                }
            }
        }
        
        return answer;
    }
}

 

 

풀이

전형적인 BFS 문제. dfs가 아닌 bfs로 풀어야 하는 이유는 최단 거리를 구해야하기 때문이다. 즉 깊이 우선으로 탐색할 경우 모든 깊이를 다 측정해야하는데, 너비 우선으로 탐색하면 해당 cnt에 도착했는지 알 수 있기 때문에 (최악의 경우가 아니고서야) 대체로 연산이 적다.