99클럽 코테 스터디 29일차 TIL (챌린저): [백준][Java] 11657 타임머신 - 골드4

 

문제 보기

https://www.acmicpc.net/problem/11657

 

 

풀이

https://mountain-noroo.tistory.com/221

99클럽 코테 스터디 4일차 TIL (챌린저): [백준][Java] 1865 웜홀 - 골드3

 

음수, 최단거리 이 키워드를 보고 아 이거 벨만 포드구나 생각이 났다.

벨만 포드에 대해서는 위 링크에서 설명한 적이 있으니 보고 오면 좋을 듯하다.

 

1번 노드로부터의 최단거리를 전부 구하고 음수로 발산할 경우 -1을 출력한다.

만약 구할 수 없는 노드가 있을 경우 해당 노드 차례에 -1을 출력한다.

 

dist[1] = 0;
for(int i = 0; i < N; i++) {
  for(int[] edge : edges) {
    if(dist[edge[0]] == Long.MIN_VALUE) continue;
    if(dist[edge[1]] != Long.MIN_VALUE && dist[edge[1]] <= dist[edge[0]] + edge[2]) continue;
    dist[edge[1]] = dist[edge[0]] + edge[2];
    if(i == N - 1) {
      isBack = true;
    }
  }
}

벨만 포드 알고리즘을 수행하는 부분이다.

INF 값은 Long.MIN_VALUE로 했다.

 

N-1 번째 거리 계산에서도 수행이 될 경우 음수로 발산하고 있다는 뜻이다.

 

if(isBack) {
  bw.write("-1\n");
} else {
  for(int i = 2; i <= N; i++) {
    if(dist[i] == Long.MIN_VALUE) {
      bw.write(-1 + "\n");
    } else {
      bw.write(dist[i] + "\n");
    }
  }
}

그 경우 -1을 출력

그렇지 않으면 모든 노드의 최단거리를 순회하며 INF 값이 남아있을 경우 -1을 출력한다.

 

 

전체 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    int M = Integer.parseInt(st.nextToken());
    List<int[]> edges = new ArrayList<>();

    while (M-- > 0) {
      st = new StringTokenizer(br.readLine());
      edges.add(new int[]{Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())});
    }

    boolean isBack = false;
    long[] dist = new long[N + 1];
    for(int i = 1; i <= N; i++) {
      dist[i] = Long.MIN_VALUE;
    }
    dist[1] = 0;
    for(int i = 0; i < N; i++) {
      for(int[] edge : edges) {
        if(dist[edge[0]] == Long.MIN_VALUE) continue;
        if(dist[edge[1]] != Long.MIN_VALUE && dist[edge[1]] <= dist[edge[0]] + edge[2]) continue;
        dist[edge[1]] = dist[edge[0]] + edge[2];
        if(i == N - 1) {
          isBack = true;
        }
      }
    }

    if(isBack) {
      bw.write("-1\n");
    } else {
      for(int i = 2; i <= N; i++) {
        if(dist[i] == Long.MIN_VALUE) {
          bw.write(-1 + "\n");
        } else {
          bw.write(dist[i] + "\n");
        }
      }
    }
    bw.flush();
    bw.close();
  }
}

 

 

GitHub 링크

https://github.com/MetroDefro/CodingTest_AutoSave/tree/main/%EB%B0%B1%EC%A4%80/Gold/11657.%E2%80%85%ED%83%80%EC%9E%84%EB%A8%B8%EC%8B%A0

CodingTest_AutoSave/백준/Gold/11657. 타임머신 at main · MetroDefro/CodingTest_AutoSave