백준 코딩테스트 1389 케빈 베이컨의 6단계 법칙
백준 코딩테스트 1389 케빈 베이컨의 6단계 법칙 — #백준코딩테스트 #백준1389번 #플로이드워셜 #케빈베이컨의6단계법칙 #개발자의도구들 AI스쿨 msa기반 ja...
#백준코딩테스트 #백준1389번 #플로이드워셜 #케빈베이컨의6단계법칙 #개발자의도구들
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다.
\본 게시글은 PC버전에 최적화되어있습니다.\
\* 하루 1코테 도전중에 있습니다. 어떤건지 궁굼하신 분들은 여기를 눌려주세요.
케빈 베이컨의 6단계 법칙
#1389 with python
문제
| 💡 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다.예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까?천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 학교 동아리 소속이다. 김도현과 민세희는 같은 학교에 다니는 사이로 서로 알고 있다. 즉, 이강호-천민호-최백준-김선영-김도현-민세희 와 같이 5단계만 거치면 된다.케빈 베이컨은 미국 헐리우드 영화배우들 끼리 케빈 베이컨 게임을 했을때 나오는 단계의 총 합이 가장 적은 사람이라고 한다.오늘은 Baekjoon Online Judge의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 찾으려고 한다. 케빈 베이컨 수는 모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합이다.예를 들어, BOJ의 유저가 5명이고, 1과 3, 1과 4, 2와 3, 3과 4, 4와 5가 친구인 경우를 생각해보자.1은 2까지 3을 통해 2단계 만에, 3까지 1단계, 4까지 1단계, 5까지 4를 통해서 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+1+2 = 6이다.2는 1까지 3을 통해서 2단계 만에, 3까지 1단계 만에, 4까지 3을 통해서 2단계 만에, 5까지 3과 4를 통해서 3단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 2+1+2+3 = 8이다.3은 1까지 1단계, 2까지 1단계, 4까지 1단계, 5까지 4를 통해 2단계 만에 알 수 있다. 따라서, 케빈 베이컨의 수는 1+1+1+2 = 5이다.4는 1까지 1단계, 2까지 3을 통해 2단계, 3까지 1단계, 5까지 1단계 만에 알 수 있다. 4의 케빈 베이컨의 수는 1+2+1+1 = 5가 된다.마지막으로 5는 1까지 4를 통해 2단계, 2까지 4와 3을 통해 3단계, 3까지 4를 통해 2단계, 4까지 1단계 만에 알 수 있다. 5의 케빈 베이컨의 수는 2+3+2+1 = 8이다.5명의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람은 3과 4이다.BOJ 유저의 수와 친구 관계가 입력으로 주어졌을 때, 케빈 베이컨의 수가 가장 작은 사람을 구하는 프로그램을 작성하시오. |
|---|
| ⌨️ 입력: 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다. 사람의 번호는 1부터 N까지이며, 두 사람이 같은 번호를 갖는 경우는 없다. |
|---|
| 🖨 출력: 첫째 줄에 BOJ의 유저 중에서 케빈 베이컨의 수가 가장 작은 사람을 출력한다. 그런 사람이 여러 명일 경우에는 번호가 가장 작은 사람을 출력한다. |
|---|
[1389번: 케빈 베이컨의 6단계 법칙
문제 케빈 베이컨의 6단계 법칙에 의하면 지구에 있는 모든 사람들은 최대 6단계 이내에서 서로 아는 사람으로 연결될 수 있다. 케빈 베이컨 게임은 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산하는 게임이다. 예를 들면, 전혀 상관없을 것 같은 인하대학교의 이강호와 서강대학교의 민세희는 몇 단계만에 이어질 수 있을까? 천민호는 이강호와 같은 학교에 다니는 사이이다. 천민호와 최백준은 Baekjoon Online Judge를 통해 알게 되었다. 최백준과 김선영은 같이 Startlink를 창업했다. 김선영과 김도현은 같은 ...
www.acmicpc.net](https://www.acmicpc.net/problem/1389)
문제풀이
floyd-warshall
이전글을 통해서 floyd-warshall을 구현하는 방법을 배워보았습니다. 이번문제는 floyd-warshll 알고리즘을 적용하는 전형적인 문제 중 하나입니다. 이와 유사한 문제가 많으니 이 문제 뿐 아니라 여러문제들을 풀어나가셨으면 좋겠습니다!
풀이순서
1. 그래프 선택
우선 A-B가 아는 사이라는 것은 둘 사이 노드간에 방향이 없는 그래프임을 의미합니다. 케빈 수는 서로 아는 사람들의 수를 의미하는데, 저는 모든 간선에 대한 가중치를 1로 계산하였습니다.
즉, 무방향 가중치 1(고정) 그래프를 선택하였습니다.
| class Graph(): def \_\_init\_\_(self): self.graph = {} self.nodes = set() def add\_node(self, node): self.nodes.add(node) def add\_edge(self, u, v): if u not in self.graph: self.graph\[u\] = {} if v not in self.graph: self.graph\[v\] = {} self.graph\[u\]\[v\] = 1 self.graph\[v\]\[u\] = 1 |
|---|
2. floyd\_warshall
이전글에 소개된 floyd-warshall 알고리즘을 그대로 적용하였습니다. 저는 기본적으로 딕셔너리 탐색을 추구하기에 이 알고리즘도 딕셔너리로 구현되어 있습니다.
구현된 알고리즘은 distance\_map을 반환하는데 이는 모든 경로에서 각 노드까지의 최단거리 결과가 담겨있는 dictionary입니다.
3. 케빈 베이컨 수 계산
문제는 케빈 베이컨 수가 가장 작은 노드에 대해 묻고 있습니다. 이는 모든 개별 노드에 대해, 서로 다른 노드 까지의 최단거리의 합이 가장 작은 노드를 의미합니다.
이를 계산하기 위해 floyd\_warshall로 계산된 distacne\_map을 반복하여 탐색하여 배열로 받아두었습니다.
| result\_map = floyd\_warshall(graph)kevins = \[\]for people in result\_map: kevin = 0 for w in result\_map\[people\].values(): kevin += w kevins.append((kevin, people)) |
|---|
4. 출력
배열에는 (케빈 수, 노드번호)가 적혀있습니다. 출력은 노드번호로 하라고 되어있으니, 이렇게 자료를 구성하였습니다.
고려해야할 예외사항은 딱 한가지가 존재합니다.
"케빈 수가 같은 노드가 두개 있는 경우 어떤 노드를 출력해야하는가? "입니다. 문제에서 더 작은 노드 번호를 출력하라고 되어있습니다.
이를 위해서 python의 lambda\_sort를 사용합니다. 사용법은 이글을 참고해주세요.
| kevins.sort(key=lambda x: (x\[0\], x\[1\]))print(kevins\[0\]\[1\]) |
|---|
후기
알고리즘 문제는 풀다보면 패턴이 비슷 비슷 한 것 같습니다.
- 그래프를 어떻게 구성 할건지, 2. 어떤 알고리즘이 필요한지 -> 문제에 따라 알고리즘을 수정해서 사용할 수 도 있습니다. 3. 출력할때 - 정렬, 반복문 등
하지만, 자주 사용하지 않으면 까먹게 되어있으니, 꾸준히 푸는것이 제일 중요하겠네요! 오늘도 열공하세요!