https://www.acmicpc.net/problem/1865
골드3
구현 방법
"한 지점에서 출발을 하여서 시간여행을 하기 시작하여 다시 출발을 하였던 위치로 돌아왔을 때, 출발을 하였을 때보다 시간이 되돌아가 있는 경우" -> 음의 사이클이 있는지 판단해 달라는 문제였다. 벨만-포드 알고리즘을 사용하면 되지만, 문제 조건을 보면 정점의 범위가 1~500 사이이고, 테스트케이스 범위가 1 ~5이다. 따라서 O(n^3)의 시간 복잡도를 가진 플로이드-워셜 알고리즘으로도 충분히 풀 수 있다고 판단했다.(500 * 500 * 500 * 5 = 625,000,000)
Floyd-Warshall 풀이 방법
주의할 점
"두 지점을 연결하는 도로가 한 개보다 많을 수도 있다. "
=> 임의의 두 정점 사이의 가중치가 여러개 입력값으로 줄 수 있는 경우가 있어서 그 중 최솟값만 인접행렬에 업데이트 해야한다.
Bellman-Ford
주의할 점
음수 가중치의 경우 단방향이기 때문에 모든 정점을 시작점으로 음수 사이클을 찾아야 한다.
가중치 갱신 과정에서 (N -1)이하에서 갱신이 일어나지 않는다면 사이클이 존재하지 않는 것으로 판단할 수 있다. -> 속도 올라감
코드
Floyd-Warshall
import java.io.*;
import java.util.*;
/**
* 백준 1865
* 웜홀
* 골드3
* https://www.acmicpc.net/problem/1865
* Floyd-Warshall
*/
public class Boj1865_FloydWarshall {
private static int INF = 10001;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int TC = Integer.parseInt(br.readLine());
while(TC-- > 0) {
st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); //지점 수
int M = Integer.parseInt(st.nextToken()); //도로 개수
int W = Integer.parseInt(st.nextToken()); //웜홀 개수
int[][] dist = new int[N + 1][N + 1];
for(int i = 1; i <= N; i++) {
Arrays.fill(dist[i], INF);
dist[i][i] = 0;
}
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
dist[a][b] = Math.min(dist[a][b], cost);
dist[b][a] = Math.min(dist[b][a], cost);
}
for(int i = 0; i < W; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
dist[a][b] = -cost;
}
floydWarshall(dist, N);
boolean isNegativeCycle = false;
for(int i = 1; i <= N; i++) {
if(dist[i][i] < 0) {
isNegativeCycle = true;
break;
}
}
if(isNegativeCycle)
sb.append("YES\n");
else
sb.append("NO\n");
}
System.out.print(sb);
}
public static void floydWarshall(int[][] dist, int n) {
for(int k = 1; k <= n; k++) {
for(int i = 1; i <= n; i++) {
if (dist[i][k] == INF) continue;
for(int j = 1; j <= n; j++) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
}
Bellman-Ford
import java.io.*;
import java.util.*;
/**
* 백준 1865
* 웜홀
* 골드3
* https://www.acmicpc.net/problem/1865
* Bellman-Ford
*/
public class Boj1865_BellmanFord {
private static class Edge {
int u; //시작 정점
int v; //끝 정점
int w; //가중치
Edge(int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
}
private static List<Edge> g;
private static int INF = 10001;
private static int N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
int TC = Integer.parseInt(br.readLine());
while(TC-- > 0) {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //지점 수
int M = Integer.parseInt(st.nextToken()); //도로 개수
int W = Integer.parseInt(st.nextToken()); //웜홀 개수
g = new ArrayList<>();
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
g.add(new Edge(a, b, cost));
g.add(new Edge(b, a, cost));
}
for(int i = 0; i < W; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
g.add(new Edge(a, b, -cost));
}
if(bellmanFord())
sb.append("YES\n");
else
sb.append("NO\n");
}
System.out.print(sb);
}
public static boolean bellmanFord() {
int[] dist = new int[N + 1];
Arrays.fill(dist, INF);
for(int i = 0; i < N - 1; i++) {
boolean updated = false;
for(Edge e : g) {
if(dist[e.u] + e.w < dist[e.v]) {
dist[e.v] = dist[e.u] + e.w;
updated = true;
}
}
if(!updated)
return false;
}
for(Edge e : g) {
if(dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
return true;
}
return false;
}
}
알고리즘 정리
Floyd-Warshall
- 모든 정점에서 모든 정점까지 최단 거리를 구함
- 음수 가중치 허용, 음수 사이클 비허용
- 시간복잡도 : O(n^3)
- 인접행렬로 표현
- 음수 사이클 탐지 가능 -> 대신 이 경우 올바른 최단 경로 계산 불가
- 음수 사이클이 있는 경우 최단 경로 계산 불가
- 어디서 음수 사이클이 발생하는지는 알 수 없음
- 시작 정점과 끝 정점은 음수 사이클이 없는 이상 비용이 0 하지만 음수 사이클이 존재하는 경우 마이스너가 됨
-> 이걸로 음수 사이클 판단
Bellman-Ford
- 음수 가중치 허용
- 시작 정점으로부터 각 점점까지 최단 경로 구하는 기법
- 음수 사이클 탐지 가능
- 시작점을 지정한 경우 -> 음의 사이클 판단 가능, 시작점 기준 최단 거리 구하기 가능
private static class Edge {
int u; //시작 정점
int v; //끝 정점
int w; //가중치
Edge (int u, int v, int w) {
this.u = u;
this.v = v;
this.w = w;
}
}
// 시작점을 지정한 경우 "dist[e.u] != INF"가 필수!!
// 이유 : 비용 갱신 시 시작점으로 출발 했는지 확인하기 때문, 시작점의 비용은 0이기 때문
public static boolean bellmanFord(int start) {
int[] dist = new int[N + 1];
Arrays.fill(dist, INF);
dist[start] = 0;
for(int i = 0; i < N - 1; i++) {
boolean updated = false;
for(Edge e : g) {
if(dist[e.u] != INF && [dist[e.u] + e.w < dist[e.v]) {
dist[e.v] = dist[e.u] + e.w;
updated = true;
}
}
if(!updated)
return false;
}
for(Edge e : g) {
if(dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
return true;
}
return false;
}- 시작점 미지정 -> 음의 사이클 판단 가능, 최단 거리는 구할 수 있지만 어디서 출발한건지 모름
// 시작점 미지정, 주로 음의 사이클 판단용으로만 쓸 때 유용
public static boolean bellmanFord() {
int[] dist = new int[N + 1];
Arrays.fill(dist, INF);
for(int i = 0; i < N - 1; i++) {
boolean updated = false;
for(Edge e : g) {
if(dist[e.u] + e.w < dist[e.v]) {
dist[e.v] = dist[e.u] + e.w;
updated = true;
}
}
if(!updated)
return false;
}
for(Edge e : g) {
if(dist[e.u] != INF && dist[e.u] + e.w < dist[e.v])
return true;
}
return false;
}
참고. 유니온 파인드 -> 사이클 판단 가능, 음수 사이클 판단은 불가
'알고리즘' 카테고리의 다른 글
| 자바 - 백준 2098 / 외판원 순회 (0) | 2024.12.05 |
|---|---|
| 자바 - 코드트리 / 빙산의 일각 (0) | 2024.10.29 |
| 자바 - 백준 2758 / 로또 (0) | 2024.10.22 |
| 자바 - 백준 1106 / 호텔 (1) | 2024.10.19 |
| 자바 - 백준 16120 / PPAP (1) | 2024.10.16 |