[TIL] 2025.02.14 플로이드 워셜

오늘의 키워드

플로이드 워셜

해당 알고리즘을 원래 알고있었지만, 시간이 좀 지나면 코드에서 세세한 부분이 잊어버리게 된다ㅠ

그래서 오랜만에 작성하면 틀렸습니다. 문구를 좀 보게되는데, 이번에는 시간초과도 뜨는 것을 보았다.

한줄 차이로 시간초과가 났는데, 오늘은 시간초과를 일으킨 한줄을 기록하고자 한다.

플로이드워셜

푼 문제는 아래와 같다

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

다익스트라로 풀면 간편하지만! 오랜만에 플로이드워셜로 풀어보고 싶었다.

 

public static void go(){
    for(int k = 1; k < N+1; k++) {
      for(int i = 1; i < N+1; i++) {
        for(int j = 1; j < N+1; j++) {
          // if(times[i][k] == 100_000_001 || times[k][j] == 100_000_001) continue;
          times[i][j] = Math.min(times[i][k] + times[k][j], times[i][j]);
        }
      }
    }
  }

여기서 주석처리된 저 한줄! 차이가 시간초과를 나게 만들었다.

N이 1000이기 때문에 충분하다고 판단했었는데.. 안되네..

 

해당 부분을 제거하면 일단 문제는 통과한다. 이유는 문제에서 " 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다." 라고 주어져있기 때문이다.

 

하지만 저 문구가 없이 가지못한다면 -1을 출력하라고 되어있었다면..?이라는 생각이 있어서 아래와 같이 수정하여 해결했다.

public static void go(){
    for(int k = 1; k < N+1; k++) {
      for(int i = 1; i < N+1; i++) {
        if(times[i][k] == 100_000_001) continue;
        for(int j = 1; j < N+1; j++) {
          if(times[k][j] == 100_000_001) continue;
          times[i][j] = Math.min(times[i][k] + times[k][j], times[i][j]);
        }
      }
    }
  }