1. 문제
https://www.acmicpc.net/problem/11657
2. 풀이 과정
최단 경로를 구하는 데, 경로의 cost가 음수가 될 수 있기 때문에 Bellman-Ford 알고리즘을 사용했다.
평소에 잘 풀어보지 않았던 유형이라서 시간이 걸렸다..
벨만-포드 알고리즘은 다익스트라와 유사한데,
다익스트라는 현재 연결된 노드에서 갈 수 있는 경로를 살펴보며 값을 업데이트하는 반면
벨만-포드 알고리즘은 모든 경로를 보면서 최단 경로를 업데이트해가는데
N-1(가능한 최대 길이)만큼 경로 업데이트를 한 후, 한 번 더 검사했을 때 더 짧은 경로가 있다면 음수로 된 사이클이 있는 것이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static class Edge {
int start, end, cost;
public Edge(int start, int end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
}
static int N, M;
static final long INF = Long.MAX_VALUE;
static Edge[] arr;
static long[] distance;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new Edge[M];
distance = new long[N + 1];
Arrays.fill(distance, INF);
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 C = Integer.parseInt(st.nextToken());
arr[i] = new Edge(A, B, C);
}
BellmanFord(1);
StringBuilder sb = new StringBuilder();
for (int i = 2; i <= N; i++) {
if (distance[i] == INF) {
sb.append("-1\n");
} else {
sb.append(distance[i]).append("\n");
}
}
System.out.println(sb);
}
public static void BellmanFord(int start) {
distance[start] = 0;
for (int i = 0; i < N; i++) {
for (Edge edge : arr) {
if (distance[edge.start] != INF && distance[edge.end] > distance[edge.start] + edge.cost) {
distance[edge.end] = distance[edge.start] + edge.cost;
}
}
}
for(Edge edge : arr) {
if (distance[edge.start] != INF && distance[edge.end] > distance[edge.start] + edge.cost) {
System.out.println("-1");
System.exit(0);
}
}
}
}
결과
'코딩문제풀이 > Baekjoon' 카테고리의 다른 글
[Java] 백준 17182번 : 우주 탐사선* (0) | 2023.01.27 |
---|---|
[Java] 백준 1525번 : 퍼즐 (0) | 2023.01.24 |
[Java] 백준 1890번 : 점프 (0) | 2023.01.13 |
[Java] 백준 21610번 : 마법사 상어와 비바라기 (0) | 2023.01.10 |
[Java] 백준 5427번 : 불 (0) | 2023.01.10 |