[Java] 최단거리 구하기 알고리즘 (가중치 있는 경우/ 없는 경우)

1. 가중치가 없을 때 → BFS

모든 간선의 비용이 같을 때 (예: 한 칸 이동 = 1)

BFS는 가까운 노드부터 차례대로 탐색하기 때문에 처음 도착한 거리가 최단거리이다.

한 칸당 이동하는 데 드는 비용이 같고,

int[][] map 환경에서 A에서 B까지 가는 데에 걸리는 최단 거리를 구하는 문제가 나오면

다음과 같이 풀면 된다.

import java.util.*;

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

    public int bfs(int[][] map) {
        int n = map.length;
        int m = map[0].length;
        
        boolean[][] visited = new boolean[n][m];
        Queue<int[]> q = new LinkedList<>();
        
        q.offer(new int[]{0, 0, 1}); // x, y, 거리
        visited[0][0] = true;
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            int x = now[0];
            int y = now[1];
            int dist = now[2];
            
            if(x == n-1 && y == m-1) return dist;
            
            for(int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                
                if(nx >= 0 && ny >= 0 && nx < n && ny < m) {
                    if(!visited[nx][ny] && map[nx][ny] == 1) {
                        visited[nx][ny] = true;
                        q.offer(new int[]{nx, ny, dist + 1});
                    }
                }
            }
        }
        return -1;
    }
}

• bfs로 풀어 Queue 선언
• Queue에는 {start, end, distance} : start에서 end까지 가는데 움직인 거리 distance를 저장한다.
• 상하좌우 보면서 움직일 수 있고, 방문한 적이 없으면 다음 좌표와 distance+1를 해서 queue에 값을 추가한다.

시간 복잡도는 O(V+E)

 

2. 가중치가 있을 때 → 다익스트라

길마다 비용이 다를 때,

가장 현재까지 비용이 적은 노드부터 탐색 → PriorityQueue 사용

import java.util.*;

class Solution {
    static final int INF = Integer.MAX_VALUE;
    static ArrayList<int[]>[] graph; // {다음정점, 가중치}
    static int[] dist;
    
    // graph에 a -> b 까지 가는 거리 저장 
    graph = new ArrayList[n + 1];
		for (int i = 1; i <= n; i++) {
		  graph[i] = new ArrayList<>();
		}
		
		// 간선 추가 (u -> v, 비용 w)
		graph[u].add(new int[]{v, w});
    
    public void dijkstra(int start, n) {
	    PriorityQueue<int[]> pq = new PriorityQueue<>({o1, o2} -> {
		    return o1[1] - o2[1]; // 비용 기준 오름차순
	    });
	    
	    dist = new int[n+1];
	    Arrays.fill(dist, INF); // 초기화 : 모든 값을 INF로 채우기 
	    
	    dist[start] = 0; // 처음 시작 index는 거리 0
	    pq.offer(new int[]{start, 0}); // 정점, 비용
	    
	    while(!pq.isEmpty()){
		    int[] now = pq.poll();
		    int node = now[0];
		    int cost = now[1];
		    
		    // 이미 더 짧은 경로가 있으면 스킵
		    if(cost > distance[node]) continue;
		    
		    for(int[] next = graph[node]) {
			    int nextNode = next[0];
			    int weight = next[1];
			    
			    int newCost = cost + weight;
			    if(newCost < distance[nextNode]) {
				    distnace[nextNode] = newCost;
				    pq.offer(new int[]{nextNode, newCost});
			    }
			    
		    }
	    }
	    
    
    }
}

• 초기화 : graph에 a -> b 까지 가는 거리 저장
• 처음 시작 위치에서 각 위치까지 걸리는 최단 거리 구하기 (dijkstra)
  • PriorityQueue<> 에 {nextNode, cost}를 저장해서 cost 기준으로 오름차순으로 정렬
  • pq에 {start, 0}을 넣고 pq가 비지 않을 때까지(while)
    • 만약 현재 cost가 distance[node] 보다 크면 continue
    • node에서 갈 수 있는 nextNode(for문)
    • 현재까지 온 cost + nextNode로 가는 weight (newCost) 가 distance[nextNode] 보다 작으면 갱신 ⇒ 처음 시작(start) 위치에서 nextNode로 갈 수 있는 최단 거리 계산

시간 복잡도 O(E logV)