[프로그래머스] 게임 맵 최단거리 - 자바

https://school.programmers.co.kr/learn/courses/30/lessons/1844

프로그래머스

문제 풀이

가장 기본적인 dfs/bfs로 문제로 이렇게 최단 거리 문제는 dfs보다 bfs 효율이 좋다.

dfs는 처음 도착지점에 도착했을 때 최소 경로인지 장담하지 못한다. 하지만 bfs는 처음 도착했을 때 최단 거리를 보장하므로 찾고나서 바로 종료하면 된다.

 

단, 이 문제처럼 각 경로의 비용이 모두 같은 경우에서만 가능한 이론이다

코드

import java.util.*;

class Node{
    int x;
    int y;
    int depth;
    Node(int x, int y, int d){
        this.x=x;
        this.y=y;
        depth=d;
    }
}
class Solution {
    public int solution(int[][] maps) {
        return bfs(maps);
    }
    static int[] dx={-1,1,0,0};
    static int[] dy={0,0,-1,1};
    
    static int bfs(int[][] maps){
        int r=maps.length;
        int c=maps[0].length;
        boolean[][] visited = new boolean[r][c];
        visited[0][0]=true;
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(0,0,1));
        
        while(!q.isEmpty()){
            Node now = q.poll();
            
            if(now.x==r-1 && now.y==c-1)
                return now.depth;
            
            for(int i=0; i<4; i++){
                int nx = now.x+dx[i];
                int ny = now.y+dy[i];
                if(nx<0 || ny<0 || nx>=r || ny>=c || visited[nx][ny] 
                   || maps[nx][ny]==0)
                    continue;
                
                visited[nx][ny]=true;
                q.add(new Node(nx, ny, now.depth+1));
            }
        }
        return -1;
    }
    
}