[백준 1238] 파티

[ 백준 1238 : 파티 ]

이건 전에 풀었던 케빈베이컨의6단계 법칙 이 문제와 똑같이 풀면된다.
n의 범위가 100에서 1000으로 늘었고 양방향이 아니라 단방향인점 빼고는 거의 일치한다.

어떤 마을에서 다른 마을을 갔다가 와야하는데 플로이드와샬 알고리즘으로 마을간의 비용(시간소비량)을 최솟값으로 맞춰놓는다면 문제없이 풀 수 있는 문제다.

1. 일단 마을간 이동하는 비용을 모두 답으로 나올 수 없는 큰 수로 셋팅한다.
2. 그 후 입력을 받으며 A마을에서 B마을로 가는 비용 중 이미 설정된 값과 비교해서 더 작은 값을 집어넣는다.
3. A마을에서 A마을로 오는 경우는 0으로 셋팅한다.
4. 이제 3중 포문을 돌린다.
5. 기본 개념은 이렇다.

A, B, C, D마을이 있다고 가정하자.
그럼
먼저 A마을을 기준으로 했을 때 A->B의 시간이 A->C->B보다 많이 걸린다면 A->B에는 A->C->B의 값을 다시 넣어주고
이런식으로 N^3번 반복하면 처음 집어넣었던 숫자가 모두 다시 세팅되어서 1에서 2,3,4 가는 가장 짧은 값, 2에서 1,3,4 가는 가장 짧은 값, 이런식으로 모두 채워진다.

그럼 이제 1~N까지 ARRAY[A~D][X] + ARRAY[X][A~D] 중 가장 큰 값을 출력하면된다.

근데 n이 1000이라서 1000^3 = 1,000,000,000???????이게 말이돼????? 10억이면 1초를 넘잖아!!!

;;;;;;
근덷 통과가되버렸다. 일단 이렇게 해도 통과가 되어버리니까 다시 푸는게 맞다고 생각한다.

그럼 이제 플로이드 와샬 알고리즘이 아니라 비용이 있는 BFS ->> 다익스트라로 풀어본다.

다익스트라 알고리즘의 기본개념은 경로와 비용이 정해져있을때 어떤 정점 하나를 정해 시작한 후 나머지 정점들마다 최단거리를 계속해서 갱신해 나가는 것입니다.
시간복잡도는 플로이드 와샬알고리즘이 O(정점^3) 이였다면 다익스트라는 O(간선*LOG(정점))입니다.

1. 한 정점을 기준으로 아직 방문하지 않은 정점들 중 비용이 가장 적은 정점을 선택한다.
2. 선택한 정점에서 인접하고 아직 방문하지 않은 정점들 비용을 갱신한다.

이를 반복하면 되는데 계속해서 가장 비용이 적은 정점만 선택해야하므로 우선순위 큐를 사용하는 것이 적절하고
아마도? 대부분 이렇게 구현하고 있을 것이라 생각합니당
그리고 값을 계속해서 갱신할 정점만큼의 배열을 선언해주어야하는데
이 문제에서는 어떤 정점에서 시작해 X까지 간 후 X에서 다시 어떤 정점으로 돌아와야하므로 갱신할 배열을 두 개 선언한 후 시작합니당.