https://www.acmicpc.net/problem/11657
정답률 25.120%
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C < 0인 경우는 타임머신으로 시간을 되돌아가는 경우이다.
1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.
3 4
1 2 4
1 3 3
2 3 -1
3 1 -2
4
3
시작 노드에서 다른 노드까지의 최단 거리를 구하는 문제이지만 간선의 가중치가 음수인 간선이 존재한다. 이는 벨만-포드 알고리즘으로 해결할 수 있다.
간선의 정보를 객체로 만들기 위해 Edge 클래스를 생성한다.
static class Edge {
int from;
int to;
int weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
그리고 다른 그래프 문제처럼 인접 리스트를 구현하는 것이 아니라 간선들의 리스트로 생성한다.
List<Edge> edges = 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 c = Integer.parseInt(st.nextToken()); //비용
edges.add(new Edge(a, b, c));
}
그리고 벨만-포드 알고리즘을 수행하는데 다음과 같은 순서로 수행한다.
static boolean bellmanFord() {
Arrays.fill(dist, INF);
dist[1] = 0; //시작 노드의 거리는 0
//노드 개수-1 만큼 반복
for (int i = 1; i < N; i++) {
//모든 간선에 대하여 거리 정보 업데이트
for (int j = 0; j < M; j++) {
Edge edge = edges.get(j);
int from = edge.from;
int to = edge.to;
//출발 노드를 방문했을 경우
if (dist[from] != INF) {
//거리 정보 업데이트
long newDist = dist[from] + edge.weight;
if (dist[to] > newDist) {
dist[to] = newDist;
}
}
}
}
//음수 사이클 확인
for (int i = 0; i < M; i++) {
Edge edge = edges.get(i);
int from = edge.from;
int to = edge.to;
if (dist[from] != INF) {
//거리 정보가 업데이트 될 경우 음수 사이클 존재
if (dist[to] > dist[from] + edge.weight) {
return true;
}
}
}
return false;
}
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
//백준
public class Main {
static final int INF = Integer.MAX_VALUE;
static List<Edge> edges = new ArrayList<>();
static long[] dist;
static int N;
static int M;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken()); //도시의 개수
M = Integer.parseInt(st.nextToken()); //버스 노선의 개수
dist = new long[N + 1];
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()); //비용
edges.add(new Edge(a, b, c));
}
StringBuilder sb = new StringBuilder();
boolean hasNegativeCycle = bellmanFord();
//음수 사이클이 존재하지 않을 경우
if (!hasNegativeCycle) {
for (int i = 2; i <= N; i++) {
if (dist[i] == INF) {
sb.append(-1).append("\n");
} else {
sb.append(dist[i]).append("\n");
}
}
} else {
sb.append(-1);
}
System.out.println(sb);
}
static boolean bellmanFord() {
Arrays.fill(dist, INF);
dist[1] = 0; //시작 노드의 거리는 0
//노드 개수-1 만큼 반복
for (int i = 1; i < N; i++) {
//모든 간선에 대하여 거리 정보 업데이트
for (int j = 0; j < M; j++) {
Edge edge = edges.get(j);
int from = edge.from;
int to = edge.to;
//출발 노드를 방문했을 경우
if (dist[from] != INF) {
//거리 정보 업데이트
long newDist = dist[from] + edge.weight;
if (dist[to] > newDist) {
dist[to] = newDist;
}
}
}
}
//음수 사이클 확인
for (int i = 0; i < M; i++) {
Edge edge = edges.get(i);
int from = edge.from;
int to = edge.to;
if (dist[from] != INF) {
//거리 정보가 업데이트 될 경우 음수 사이클 존재
if (dist[to] > dist[from] + edge.weight) {
return true;
}
}
}
return false;
}
static class Edge {
int from;
int to;
int weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}
}