N개의 도시와 한 도시에서 출발해 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작 도시, B는 도착 도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닐 때가 있다. C = 0일 경우에는 순간 이동을 할 때, C < 0일 경우에는 타임 머신으로 시간을 되돌아갈 때다. 1번 도시에서 출발해 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.
(시간 제한 1초)
입력
1번째 줄에 도시의 개수 N(1 ≤ N ≤ 500). 버스 노선의 개수 M(1 ≤ M ≤6,000)이 주어진다. 2번째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C(1 ≤ A,B ≤ N, -10,000 ≤ C ≤ 10,000).
출력
만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 1번째 줄에 -1을 출력한다. 그렇지 않다면 N-1개 줄에 걸쳐 각 줄의 1번 도시에서 출발해 2번 도시, 3번 도시, ... N번 도시로 가는 가장 빠른 시간을 순서대로 출력한다. 만약 이 도시로 가는 경로가 없다면 -1을 출력한다.
예제 입력
3 4 // 노드, 에지
1 2 4
1 3 3
2 3 -4
3 1 -2
예제 출력
-1
1단계 - 문제 분석하기
시작점 및 다른 노드와 관련된 최단 거리를 구하는 문제지만, 특이한 점은 에지에 해당하는 이동하는 시간이 양수가 아닌 0또는 음수가 가능하다는 점이다. 이렇게 시작점에서 다른 노드와 관련된 최단 거리를 구하는데, 에지가 음수가 가능할 때는 벨만-포트 알고리즘을 사용하면 된다.
2단계 - 손으로 풀어 보기
1 에지 리스트에 에지 데이터를 저장한 후 거리 배열을 초기화한다.
2 다음 순서에 따라 벨만-포트 알고리즘을 수행한다.
- 모든 에지와 관련된 정보를 가져온 후 다음 조건에 따라 거리 배열의 값을 업데이트한다.
- 출발 노드가 방문한 적이 없는 노드(출발 노드 거리 == INF)일 때 값을 업데이트하지 않는다.
- 출발 노드의 거리 배열값 + 에지 가중치 < 종료 노드의 거리 배열값일 때 종료 노드의 거리 배열값을 업데이트한다.
- '노드 개수 -1' 번 만큼 1을 반복한다.
- 음수 사이클 유무를 알기 위해 모든 에지에 관해 다시 한번 1을 수행한다. 이때 한 번이라도 값이 업데이트되면 음수 사이클이 존재한다고 판단한다.
3 음수 사이클이 존재하는지 확인해보기 위해 에지를 한 번씩 다시 사용한다. 음수 사이클이 존재하면 -1을, 존재하지 않으면 거리 배열의 값을 출력한다. 단, 거리 배열의 값이 INF일 경우에는 -1을 출력한다.
3단계 - sudo코드 작성하기
N(노드 개수) M(에지 개수)
distance(거리 저장 배열)
edges(에지 리스트 배열)
거리 배열 INF로 초기화
for(에지 개수)
{
에지 리스트 배열에 에지 정보 저장
}
거리 배열의 출발 노드를 0으로 초기화
for(노드 개수-1 만큼 반복)
{
for(에지 개수만큼 반복)
{
현재 에지 데이터 가져오기
if(출발 노드가 INF가 아님 && 종료 노드 거리값 > 출발 노드 거리값 + 에지 가중치 라면)
{
종료 노드 거리값 = 출발 노드 거리값 + 에지 가중치
}
}
}
for(에지 개수만큼 반복)
{
현재 에지 데이터 가져오기
if(출발 노드가 INF가 아님 && 종료 노드 거리값 > 출발 노드 거리값 + 에지 가중치 라면)
{
음수 사이클이 존재함
}
}
if(음수 사이클이 존재하면)
{
-1 출력
}else
{
거리 배열 출력(INF면 -1 출력)
}4단계 - 코드 구현하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Q59 {
public static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
int[] distance = new int[N+1];
for(int i = 1; i < N+1; i++){
distance[i] = INF;
}
Edge59[] edge = new Edge59[M];
for(int i = 0; i < M; i++){
st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
edge[i] = new Edge59(S, E, V);
}
distance[1] = 0;
for(int i = 0; i < N-1; i++){
for(int j = 0; j < M; j++){
Edge59 now = edge[j];
if(distance[now.start] != INF && distance[now.end] > distance[now.start] + now.value){
distance[now.end] = distance[now.start] + now.value;
}
}
}
boolean cycle = false;
for(int i = 0; i < M; i++){
Edge59 now = edge[i];
if(distance[now.start] != INF && distance[now.end] > distance[now.start] + now.value){
cycle = true;
}
}
if(cycle){
System.out.println(-1);
}else {
for(int i = 2; i < N+1; i++){
if(distance[i] == INF)
System.out.println(-1);
else
System.out.println(distance[i]);
}
}
br.close();
}
}
class Edge59{
int start;
int end;
int value;
Edge59(int start, int end, int value){
this.start = start;
this.end = end;
this.value = value;
}
}
- Do it! 알고리즘 코딩테스트 자바 편
