풀이: 프로그래머스.49191.순위

[changicho]

49191. 순위

링크

난이도	완료(명)
lv3	1004

설계

시간복잡도

플로이드 와샬 알고리즘을 이용해서 모든 정점 쌍에 대한 최단거리를 구할 수 있다.

시간 복잡도 : O(V^3) (V : 정점의 개수)

정점의 갯수는 최대 100 이므로 V^3 으로 검색 가능하다.

공간복잡도

100^2 크기의 int형 배열을 선언한다.

연결 관계는 단순히 숫자 1로 표시가 가능하다. 그 외의 연결 구조를 파악할 수 없는 경우는

INF로 표기한다.

INF는 충분히 큰 수로 표기한다.

플로이드-워셜 알고리즘

이 문제는 백준.2458.키 순서와 같다.

플로이드 워셜 알고리즘은 모든 정점 쌍에 대한 최단거리를 구하는 알고리즘이다.

플로이드 워셜 알고리즘을 수행하면, 모든 정점에 대한 연결 여부와 거리를 판단할 수 있다.

따라서 플로이드 워셜 알고리즘을 통해 모든 정점상의 거리를 구한다.

시간 복잡도 : O(V^3) (V : 정점의 개수)

V가 크면 사용하지 못함에 주의하자

특징

• 단 방향 그래프
• 어떤 특정 정점을 거쳤을 때의 경로가 최단이라면 table을 update한다.
• 이전에 구했던 최단 경로를 통해 새로운 최단 경로를 찾는 방식으로 진행된다.

// costs[from][to]
int costs[MAX_SIZE][MAX_SIZE];

void floyd_warshall() {
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      for (int k = 1; k <= N; k++) {
        if (costs[j][i] != INF && costs[i][k] != INF) {
          costs[j][k] = min(costs[j][k], costs[j][i] + costs[i][k]);
        }
      }
    }
  }

  // set self distance is 0;
  for (int i = 1; i <= N; i++) {
    costs[i][i] = 0;
  }
  return;
}

단방향 그래프

키 순서에 대한 그래프이므로 그래프는 단방향 그래프이다.

거리를 구한 그래프에서, [i][j]의 거리와 [j][i]거리 모두 무한인 경우가 (정점 i와 j는 절대 연결되지않으) 존재하면 이는 답이 될 수 없다.

1부터 N까지 n을 순회하고, j또한 한번 더 순회하며 [n][j]와 [j][n]이 모두 무한인지 비교하고, 모두 무한인 경우가 없는 경우 정답을 증가시킨다.

고생한 점