DP 정리

최단 경로

🔍 개요

• 그래프 조건에 따라 알고리즘 선택
  1. 가중치 없음 → BFS
  2. 가중치 양수 → 다익스트라(Dijkstra)
  3. 음수 가중치 가능 → 벨만-포드(Bellman-Ford)
  4. 모든 접점 쌍 최단 거리 → 플로이드-워셜(Floyd-Warshall)

---

📚 알고리즘 종류

1. BFS (가중치 없는 최단 경로)

• 아이디어 : 간선의 비용이 모두 1이라면, BFS로 탐색 순서가 곧 최단거리

class BFSShortestPath {
	static int bfs(int start, int end, List<List<Integer>> graph) {
		int n = graph.size();
		int[] dist = new int[n];
		
		Arrays.fill(dist, -1);
		
		Queue<Integer> q = new LinkedList<>();
		q.offer(start);
		dist[start] = 0;
		
		while(!q.isEmpty()) {
			int cur = q.poll();
			if(cur == end) {
				return dist[cur];
			}
			
			for(int next : graph.get(cur)) {
				if(dist[next] == -1) {
					dist[next] = dist[cur] + 1;
					q.offer(next);
				}
			}
		}
		return -1;
	}
}

2. 다익스트라 알고리즘 (Dijkstra)

• 조건 : 간선 가중치 >= 0
• 아이디어 : 시작점에서 가장 가까운 정점부터 확정 → 인접 정점 거리 갱신
• 구현 : 우선순위 큐(힙) 사용

class Dijkstra {
	static class Node implements Comparable<Node> {
		int v;
		int cost;
		
		Node(int v, int cost) {
			this.v = v;
			this.cost = cost;
		}
		
		public int compareTo(Node o) {
			return this.cost - o.cost;
		}
	}
	
	static int[] dijkstra(int n, List<List<Node>> graph, int start) {
		int[] dist = new int[n+1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start] = 0;
		
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.offer(new Node(start, 0));
		
		while(!pq.isEmpty()) {
			Node cur = pq.poll();
			if(cur.cost > dist[cur.v]) {
				continue;
			}
			
			for(Node next : graph.get(cur.v)) {
				int newCost = cur.cost + next.cost;
				if(newCost < dist[next.v]) {
					dist[next.v] = newCost;
					pq.offer(new Node(next.v, newCost));
				}
			}
		}
		return dist;
	}
}

3. 플로이드-워셜 (Floyd-Warshall)

• 조건 : 모든 정점 쌍 최단 거리 (N이 작을 때, 보통 N ⇐ 500)
• 아이디어 : 점화식 → dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

class FloydWarshall {
	static void floyd(int n, int[][] dist) {
		for(int k = 1; k <= n; k++) {
			for(int i = 1; i <= n; i++) {
				for(int j = 1; j<= n; j++) {
					if(dist[i][k] != 1e9 && dist[k][j] != 1e9) {
						dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
					}
				}
			}
		
		}
	}
}