- 오늘의 학습 키워드 : 벨만-포드 알고리즘
[문제 이름 : 웜홀 (백준 1865, G3)]
문제 url : https://www.acmicpc.net/problem/1865
내가 작성한 코드는 아래와 같다.
import java.io.*;
import java.util.*;
public class Main {
static final long INF = Long.MAX_VALUE;
static List<Edge> edges;
static int N, M, W;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
while (T-- > 0) {
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
W = Integer.parseInt(st.nextToken());
edges = new ArrayList<>();
// 도로 정보 입력
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(st.nextToken());
// 양방향 도로 정보 저장
edges.add(new Edge(start, end, time));
edges.add(new Edge(end, start, time));
}
// 웜홀 정보 입력
for (int i = 0; i < W; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int time = Integer.parseInt(st.nextToken());
// 음의 가중치
edges.add(new Edge(start, end, -time));
}
if (hasNegativeCycle()) {
sb.append("YES\n");
} else {
sb.append("NO\n");
}
}
System.out.print(sb);
}
static boolean hasNegativeCycle() {
long[] dist = new long[N + 1];
Arrays.fill(dist, INF);
for (int i = 1; i <= N; i++) {
// 각 노드를 시작점으로 설정
dist[i] = 0;
boolean updated = false;
// 벨만-포드 수행
for (int j = 0; j < N - 1; j++) {
updated = false;
for (Edge edge : edges) {
if (dist[edge.start] != INF && dist[edge.end] > dist[edge.start] + edge.time) {
dist[edge.end] = dist[edge.start] + edge.time;
updated = true;
}
}
for(long num : dist) {
if(num == Long.MAX_VALUE) continue;
System.out.print(num + " ");
}
System.out.println();
if (!updated) break; // 더 이상 갱신이 일어나지 않으면 중단
}
// 한 번 더 확인하여 음의 사이클 존재 여부 판별
for (Edge edge : edges) {
if (dist[edge.start] != INF && dist[edge.end] > dist[edge.start] + edge.time) {
return true; // 음의 사이클 존재
}
}
}
return false; // 음의 사이클 없음
}
static class Edge {
int start, end;
int time;
Edge(int start, int end, int time) {
this.start = start;
this.end = end;
this.time = time;
}
}
}
벨만-포드 알고리즘
- 그래프의 최단 경로를 구하는 알고리즘이다.
- 하나의 정점에서 출발하는 최단 거리를 계산한다.
- 음의 가중치를 허용하며, 이때 음수 사이클이 존재하지 않아야 한다.
- O(nm)의 시간복잡도를 가지며, 동적 계획법에 기반한 코드를 작성한다.
구현 과정
dist[]라는 1차원 배열이 쓰이는데, 이는 출발지로부터 최단 거리를 기록하는 1차원 배열이다.
정점의 개수 n만큼, 하위 과정을 반복한다.
1. 간선 m개를 하나씩 모두 살펴본다. 현재 간선의 가중치를 cost(v, w)라고 한다면, 출발 정점은 v, 도착 정점은 w이다.
2. dist[v]는 현재까지 계산한 출발지에서 v까지의 최소 거리를 저장한다. dist[v]가 무한대가 아닐 경우, 3을 진행한다.
3. dist[v] = min(3[1], 3[2])를 진행한다.
- 3[1] : dist[v] : 지금까지 계산한 v에 도착하는 최단 거리
- 3[2] : dist[w] + cost[v,v] : w에 도착하는 최단거리 + w에서 v로 가는 간선의 가중치
풀이 과정 (풀이 시간 : 1시간 30분)
1. 지점 수, 도로 수, 웜홀 수를 테스트 개수에 맞게 입력받는다. 이때, 도로 정보 입력은 양방향, 웜홀 정보 입력은 단방향으로 입력받는다.
2. dist[i]는 정점 i까지 최소 비용(혹은 최소 거리)을 의미한다. 벨만-포드 알고리즘에서는 한 정점에서 다른 모든 정점까지의 최단 거리를 구하게 되는데, 이때 dist 배열을 사용하여 해당 정보를 저장한다. 초기에는 모두 최대값으로 설정하여 각 정점의 거리 정보를 초기화하고, 각 정점을 시작점으로 설정하며 dist[i]=0으로 반복문을 시작한다. 이때, 정점의 개수가 N개라면, 출발점인 정점을 제외한 나머지 정점을 반복해야 하므로 N-1번 반복한다.
3. dist[start]가 MAX_VALUE가 아니고, dist[end] > dist[start] + time인 경우라면, 최단 거리를 갱신할 수 있다는 뜻이므로
dist[end] = dist[start] + time; 으로 갱신한다. 이때, updated 플래그를 통해 더 이상 값의 변경이 없을 시 반복을 종료한다.
4. 음의 사이클 여부를 판단해야 하므로, 벨만-포드 알고리즘 적용 후 모든 정점에서 한 번 더 모든 간선을 탐색한다.
5. 만약 N-1번 반복 이후에도, dist[end] > dist[start] + time이라면, 이는 음의 사이클임을 의미한다.
내일은 네트워크 전공 과목에 대해 공부할 예정이다.