섹션 9 Greedy - 5. 다익스트라 알고리즘

문제 설명

가중치 방향 그래프에서 1번 정점에서 출발하여 각 정점까지의 최소 거리 비용을 구하는 문제입니다.
경로가 존재하지 않는 정점은 "impossible"로 출력합니다.

---

입력 & 출력

• 입력
  • 첫 줄: 정점의 수 N (1 ≤ N ≤ 20), 간선의 수 M
  • 다음 M줄: a b c → a번 정점에서 b번 정점으로 가는 간선의 비용은 c
• 출력
  • 1번 정점에서 출발해 각 정점까지 가는 최소 거리 출력
  • 경로가 없으면 "impossible" 출력

입력 예시
6 9
1 2 12
1 3 4
2 1 2
2 3 5
2 5 5
3 4 5
4 2 2
4 5 5
6 4 5

출력 예시
2 : 11
3 : 4
4 : 9
5 : 14
6 : impossible

---

해결 방법

• 다익스트라 알고리즘은 가중치가 양수인 그래프에서 최단 경로를 구할 때 사용하는 대표적인 알고리즘입니다.
• PriorityQueue(최소 힙)를 활용해 가장 비용이 적은 정점부터 탐색합니다.
• 방문한 노드보다 더 작은 비용으로 도달 가능한 경우에만 갱신합니다.

---

코드 구현

class Edge implements Comparable<Edge> {
	public int vex, cost;
	Edge(int vex, int cost) {
		this.vex = vex;
		this.cost = cost;
	}
	public int compareTo(Edge o) {
		return this.cost - o.cost;
	}
}

public class Problem5 {
	static int n, m;
	static ArrayList<ArrayList<Edge>> graph;
	static int[] dis;

	public void solution(int v) {
		PriorityQueue<Edge> pQ = new PriorityQueue<>();
		pQ.offer(new Edge(v, 0));
		dis[v] = 0;
		while (!pQ.isEmpty()) {
			Edge tmp = pQ.poll();
			int now = tmp.vex;
			int nowCost = tmp.cost;
			if (nowCost > dis[now]) continue;
			for (Edge ob : graph.get(now)) {
				if (dis[ob.vex] > nowCost + ob.cost) {
					dis[ob.vex] = nowCost + ob.cost;
					pQ.offer(new Edge(ob.vex, nowCost + ob.cost));
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		graph = new ArrayList<>();
		for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());
		dis = new int[n + 1];
		Arrays.fill(dis, Integer.MAX_VALUE);
		for (int i = 0; i < m; i++) {
			int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
			graph.get(a).add(new Edge(b, c));
		}
		new Problem5().solution(1);
		for (int i = 2; i <= n; i++) {
			System.out.println(i + " : " + (dis[i] == Integer.MAX_VALUE ? "impossible" : dis[i]));
		}
		sc.close();
	}
}

---

주요 코드 설명

• Edge 클래스
  • 그래프의 간선을 표현 (도착 정점 vex, 비용 cost)
  • Comparable을 구현하여 PriorityQueue에서 비용이 작은 순으로 꺼낼 수 있도록 정렬
• graph
  • 인접 리스트 형태의 그래프 구조 (ArrayList<ArrayList<Edge>>)
  • graph.get(a)는 a번 정점에서 출발하는 모든 간선 리스트를 가짐
• dis 배열
  • dis[i]: 1번 정점에서 i번 정점까지의 최소 거리를 저장
  • 처음에는 모두 Integer.MAX_VALUE로 초기화 → 아직 방문하지 않음
• solution(int v)
  • 다익스트라 알고리즘 실행 함수
  • 시작점 v(1번 정점)에서 우선순위 큐에 (정점, 0) 넣고 시작
  • 우선순위 큐에서 가장 비용이 적은 정점을 꺼내며 인접 정점을 탐색
    • nowCost > dis[now]이면 이미 더 짧은 경로로 방문했으므로 스킵
    • 더 짧은 거리로 갈 수 있으면 dis 갱신하고 큐에 넣음
• main() 함수
  • 정점 수 n, 간선 수 m 입력
  • 그래프 초기화 및 간선 정보 입력
  • 1번 정점에서 다익스트라 실행
  • 2번부터 n번 정점까지의 최단 거리 출력
    • dis[i] == Integer.MAX_VALUE면 도달할 수 없으므로 "impossible" 출력

---

시간 복잡도

• 정점 수 N, 간선 수 M일 때
• 우선순위 큐 연산 (삽입/삭제): O(log N)
• 모든 정점 처리: 최대 N번 → O(N log N)
• 모든 간선 확인: 각 간선마다 큐 삽입 가능 → O(M log N)
• 총 시간 복잡도: O((N + M) log N)
• 이 문제는 N ≤ 20, M ≤ 100 이므로 충분히 빠르게 처리 가능

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런