[프로그래머스] 합승 택시 요금

아 너무 어렵다...

그래프가 나오길래 dfs로 푸는건가 했는데 풀이를 보니까 아니었다..

dp 문제인 것 같다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/72413

프로그래머스

i -> j로 가려면 

i) i -> j 로 바로 가거나

ii) i -> k -> j 로 k를 거쳐서 가거나 

둘 중 하나이므로 이를 이용하여 해결하면 되는 문제인 듯 한데

 

처음에 이렇게 했다가 안되어서 다시 풀이를 읽어봤다.

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    if (matrix[i][j] < INF) {
      for (int k = 0; k < n; k++) {
        if (matrix[i][k] < INF && matrix[k][j] < INF) {
          matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][i]);
        }
      }
    }
  }
}

바보같이 i와 j간의 간선이 없는 경우에는 계산하면 안된다고 생각해버렸기 때문이다..

 

아 그리고 마지막에 답 구할 때 <long long>을 빼먹으면 답이 나오지 않는다.

왜 long long을 쓰나 했는데 지금보니까 오버플로우가 발생하기 때문인 듯 하다.