BFS랑 다익스트라 차이점 ⇒ 가중치 여부(음수 가중치는 고려 X → 음수 가중치는 벨만포드)
가중치가 없으면 BFS, 가중치가 있으면 다익스트라 사용
BFS로는 최소 비용을 구할 수 없다.
물론, 노드 수와 가중치가 많이 작다면 더미 노드를 만들어서 구현할 수는 있다.
다익스트라로 접근하기
거리 배열 초기 상태
시작 노드를 1번으로 했기 때문에 dist[1] = 0, 나머지는 매우 큰 값으로 초기화하고 시작
1
2
3
4
5
6
7
0
∞
∞
∞
∞
∞
∞
거리가 제일 작은 1번 노드부터 시작
1번 방문 처리 & 주변 노드 거리 갱신
1
2
3
4
5
6
7
0
1
500
100
∞
∞
∞
방문 체크가 안 된 노드 중 거리가 제일 작은 2번 노드 탐색
2번 방문 처리 & 주변 노드 거리 갱신
거리 갱신할 때 1번 노드 부터 해당 노드까지 거리 중 최솟값으로 갱신한다.
1
2
3
4
5
6
7
0
1
500
100
2
11
∞
그 다음으로 거리가 제일 작은 5번 노드 탐색
5번 방문 처리 & 주변 노드 거리 갱신
1
2
3
4
5
6
7
0
1
500
100
2
11
∞
그 다음으로 거리가 제일 작은 6번 노드 탐색
6번 방문 처리 & 주변 노드 거리 갱신
1번→4번은 거리가 100, 1번→2번→6번→4번은 거리가 31로 더 작으므로 dist[4]를 갱신해준다.
1
2
3
4
5
6
7
0
1
500
31
2
11
∞
그 다음으로 거리가 제일 작은 4번 노드 탐색
4번 방문 처리 & 주변 노드 거리 갱신
1
2
3
4
5
6
7
0
1
500
31
2
11
1031
그 다음으로 거리가 제일 작은 3번 노드 탐색
3번 방문 처리 & 주변 노드 거리 갱신
1
2
3
4
5
6
7
0
1
500
31
2
11
1031
그 다음으로 거리가 제일 작은 7번 노드 탐색
7번 방문 처리 & 주변 노드 거리 갱신
1
2
3
4
5
6
7
0
1
500
31
2
11
1031
최종적으로 1번부터 4번까지 최소 거리는 31(dist[4])가 된다.
코드 기본형
import java.io.*;
import java.util.*;
public class Main {
static int N, E;
static ArrayList<Node>[] list;
static boolean[] visited;
static int[] dist;
static class Node {
int to;
int d;
Node(int to, int d) {
this.to = to;
this.d = d;
}
}
static void dikj(int start) {
int min, cur, nxt, nd;
for (int i = 0; i < N; i++) {
min = 1 << 30;
cur = 0;
// 방문하지 않은 노드 중 거리가 가장 작은 노드 찾기
// N*N
for (int j = 1; j < N + 1; j++) {
if (!visited[j] && dist[j] < min) {
min = dist[j];
cur = j;
}
}
// cur 노드 방문 처리
visited[cur] = true;
// cur 노드 주변 거리 갱신 -> 더 작은 거리로 갱신
// 2*M
for (int j = 0; j < list[cur].size(); j++) {
// nxt : cur노드와 연결된 노드
nxt = list[cur].get(j).to;
// nd : cur노드까지 거리 + cur ~ 연결된 노드까지 거리
nd = dist[cur] + list[cur].get(j).d;
// 1번부터 ~ nxt노드 까지 거리 dist[nxt]를 작은 값으로 갱신
dist[nxt] = Math.min(dist[nxt], nd);
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
list = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
list[i] = new ArrayList<>();
}
int v1, v2, d;
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
list[v1].add(new Node(v2, d));
list[v2].add(new Node(v1, d));
}
dist = new int[N + 1];
Arrays.fill(dist, 1 << 30);
dist[1] = 0;
visited = new boolean[N + 1];
dikj(1);
System.out.println(dist[4]);
System.out.println(Arrays.toString(dist));
}
}
위 코드의 시간 복잡도
E : 간선 수, V : 노드 수
O( V * V + 2 * E) => O(V * V)
각 노드당 한 번씩 순회하면서 돌게 되면, 해당 노드와 연결된 간선들을 방문하게 되는데, 이 때 총 2번 카운팅 됨 → 예를 들어, 1번과 2번 사이에 있는 간선은 1번 노드 방문할 때, 2번 노드 방문할 때 각각 한 번씩 카운팅 됨.
V*V 을 줄이고 싶다 → 거리값이 가장 작은 노드 번호를 구하는 상황을 빠르게 구하고 싶다. => PriorityQueue 사용
개선된 코드
import java.io.*;
import java.util.*;
public class Main {
static int N, E;
static ArrayList<Node>[] list;
static boolean[] visited;
static int[] dist;
static class Node implements Comparable<Node> {
int to;
int d;
Node(int to, int d) {
this.to = to;
this.d = d;
}
// 거리 기준 오름차순
@Override
public int compareTo(Node o) {
return this.d - o.d;
}
}
static void dikj(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
int cur, nxt, nd;
while (!pq.isEmpty()) {
cur = pq.poll().to;
if(visited[cur]) continue;
visited[cur] = true;
for (Node node : list[cur]) {
nxt = node.to;
nd = dist[cur] + node.d;
dist[nxt] = Math.min(dist[nxt], nd);
pq.offer(new Node(nxt, dist[nxt]));
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
list = new ArrayList[N + 1];
for (int i = 0; i < N + 1; i++) {
list[i] = new ArrayList<>();
}
int v1, v2, d;
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
d = Integer.parseInt(st.nextToken());
list[v1].add(new Node(v2, d));
list[v2].add(new Node(v1, d));
}
dist = new int[N + 1];
Arrays.fill(dist, 1 << 30);
dist[1] = 0;
visited = new boolean[N + 1];
dikj(1);
System.out.println(dist[4]);
}
}
위 코드의 시간 복잡도
O( ElogV)
현재 노드에 연결된 모든 간선을 E개만큼 확인하고, 우선순위 큐에서 간선을 순회하는 과정은 logE정도 걸린다.
