[백준 1389] 케빈 베이컨의 6단계 법칙

[ 백준 1389 : 케빈 베이컨의 6단계 법칙 ]

한 지점을 기준으로 목표점에 얼마나 많은 간선을 지날 수 있는지를 묻는다.
그리고 그 수의 합이 가장 작은 기준 지점이 어떤 점인지를 묻는 문제이다.

N이 100이다.
1을 기준으로 하고 1 이 이어진 지점이 100개라고 봤을때 총 100번을 탐색하고 그 100개는 또 다시 100개를 본다.
최악의 경우에도 100^3밖에 안되므로 1초안에 충분히 들 수 있음을 확인 할 수 있다.

그럼 그냥 방문 표시건 뭐건 무조건 다 본다. 근데 문제가 쉽다.
무조건 한 A라는 점에서 이어진 B라는 지점으로 가는 가중치는 1이다.

내가 푼 방식은 일단 이차원 배열을 만든다. [101][101] 그리고 전체에 무한히 큰 수 이 문제에서는 0x3f3f3f3f를 줬다.
대략 19억정도 된다.

그리고 입력 할 때 [a][b] 와 [b][a] 에 가중치 1씩 준다. 그리고 [a][a]같은 자기 자신에게 오는 점은 0으로 준다.

이제 순차적으로 보면서 최솟값만 저장하면된다.

일단 이 문제의 테스트 케이스를 보면
5 5
1 3
1 4
4 5
4 3
3 2
이런식으로 되어 있다.

1에서 5로 가려면 간선 총 2개가 필요하다.

그럼 3중 반복문을 이용한다.
일단 1을 기준으로 보면
1->1->1 : 0이최소이므로 [1][1]=0이된다.
....
..
1->4->5 : 이런 경우를 보면 [1][5] 는 0x3f3f3f3f가 되어 있을 것이다. 하지만 [1][4]+[4][5] 는? 총 2가 나오므로
[1][5] 와 [5][1] 에 2를 저장한다.

한 개 더 봐보자

2->3->4->5 는?

일단 포문을 돌면서 2까지 오기 전에 [1][3] 이나 [1][4] [3][4] 등등을 지나치면서 왔을 것이다.
그럼 이미 배열에 저장되어있고 만약 [2][5]가 0x3f3f3f3f로 되어있다면
[2][5] > [2][3]+[3][5] 이므로 [2][5] = [2][3] + [3][5] 가된다.

이런식으로 정점 N개가 있고 거리가 주어져 있을때 3중 반복으로 모든 정점간 거리를 구하는 알고리즘이 따로 있다.
플로이드 와샬 알고리즘인데 대부분 플로이드라고 부르더라..

근데 딱히 플로이드 와샬알고리즘을 몰랐더라도 조금만 생각해보면 다들 풀 수 있다.
나도 그랬었는데... 플로이드라는 것이 이런거구나 알면 이런 류는 생각없이 금방 푼다.