1389번: 케빈 베이컨의 6단계 법칙
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻
www.acmicpc.net
그래프의 탐색 문제이다. 너비 우선, 깊이 우선 둘 다 가능할 것 같지만 너비 우선 탐색의 구현이 더 간단하여 BFS를 사용하였다.
문제의 예시는 좌측과 같은 형태의 그래프로 표현 가능하다.
각 간선의 비용을 1이라 가정하고, N번 노드에서 출발하여 다른 노드들로 이동하는 비용의 합이 N번 노드의 케빈 베이컨 수 가 된다.
BFS를 이용해 1번 노드의 케빈 베이컨 수 를 구해보자.
1번 노드에서 1번 노드로 이동하는 비용은 0이다.
이후 1번 노드를 큐에 넣어주자.
이 다음부터는 큐의 가장 앞쪽 값을 반복적으로 탐색해 나간다.
큐의 가장 앞 값을 꺼내보니 4번 노드와 3번 노드를 탐색 가능함을 알 수 있다.
4번 노드는 기존에 방문하지 않았던 노드이므로 방문 여부와 비용을 갱신해준다.
비용과 방문 여부가 모두 갱신된 이후에 해당 노드를 큐에 넣는다.
3번 노드 또한 같은 동작을 수행한다. 이후 1번 노드에서 탐색 가능한 모든 경로를 탐색하였으므로 1번 노드는 큐에서 삭제해준다.
5번 노드의 비용과 방문 여부를 갱신한 이후 큐에 넣어준다.
이때 4번 노드에서 3번 노드로 이동이 가능하지만, 이미 방문한 노드 이기 때문에 중복해서 처리되지 않도록 한다.
이렇게 1번 노드에서 시작한 BFS를 수행한 결과, 다른 노드로 이동하기 위한 비용의 합을 구할 수 있다.
즉 1번 노드의 케빈 베이컨 수는 6이다.
위의 동작을 모든 노드를 대상으로 수행하면 모든 노드의 케빈 베이컨 수를 구할 수 있다.
code
GitHub - YoungWoo93/algorithmOnlineJudge: 알고리즘 온라인 저지
알고리즘 온라인 저지. Contribute to YoungWoo93/algorithmOnlineJudge development by creating an account on GitHub.
github.com
'알고리즘 온라인 저지 > BOJ' 카테고리의 다른 글
| BOJ 15711번 환상의 짝꿍 (0) | 2022.05.17 |
|---|---|
| BOJ 11057번 오르막 수 (0) | 2022.05.12 |
| BOJ 7576 토마토 (0) | 2022.02.10 |
| BOJ 11054 가장 긴 바이토닉 부분 수열 (0) | 2022.02.10 |
| BOJ 2042번 구간 합 구하기 (0) | 2022.02.07 |
