Life Engineering
[BOJ 1389] 케빈 베이컨의 6단계 법칙 (Python3) 본문
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
from collections import deque
N, M=map(int, input().split())
graph=[set() for _ in range(N+1)]
visited=[False]*(N+1)
result=0
array=[]
for _ in range(M):
a,b=map(int, input().split())
graph[a].add(b)
graph[b].add(a)
def bfs(i):
result=0
queue=deque()
queue.append((i,0))
visited[i]=True
while queue:
pos, cnt=queue.popleft()
result+=cnt
for i in graph[pos]:
if not visited[i]:
queue.append((i,cnt+1))
visited[i]=True
return result
for i in range(1,N+1):
visited=[False]*(N+1)
array.append(bfs(i))
print(array.index(min(array))+1)
|
cs |
문제들이 잘 안풀려서 힘든 날이었다.. 원래 "치즈" 풀려고 했는데 문제 조건을 잘못 이해한채로 몇시간째 고민하는 바람에... 헤헿 그 문제는 들여다보기 싫어서 별표만 쳐놈 ㅎㅎ
암튼.. 이 문제!는 첨엔 DFS로 탐색해서 count 값을 증가시켜 저장하는 형태로 풀려 했다가.. 그렇게 했는데 답이 틀린 걸 알고 그 방법은 깊이 탐색하는 방법이기 때문에 돌아서 값을 체크하는 법임을 깨달았다.. 즉 1-4에서 거리가 1인데, DFS에서는 3으로 체크한다는것!
아 그래서 BFS구나 깨달았다!
(사람의 번호, 카운트 값)을 저장해서 인접한 사람을 만날때마다 카운트+1 해주고 그 큐에 담긴 모든 아이템에 대해 그 카운트 값을 더해서 케빈 베이컨의 수를 리턴한다.
--아 구글링해보니 DFS로 푼사람들도 많네 ^&^;;
아래 소스코드 출처: hy38.github.io/BOJ-1389
이 분꺼 참조해 보자면, DFS로 각 지점 간 최단거리를 구하는 방식을 썼다.
DFS로 각 지점 간 최소 거리를 구해준다. DFS로 재귀 호출할 때 c라는 변수를 이용해 카운트를 해준 뒤, min 값을 비교한다.
DFS로 경우의 수 찾는 것과 비슷한 패턴이다.!
'Problem Solving' 카테고리의 다른 글
[BOJ 2206] 벽 부수고 이동하기 (Python3) (0) | 2021.02.20 |
---|---|
[BOJ 2805] 나무 자르기(Python3) (0) | 2021.02.19 |
[BOJ 1931] 회의실 배정 (Python 3) (0) | 2021.02.18 |
[BOJ 6603] 로또 (Python3) (0) | 2021.02.17 |
[코딩테스트 대비 커리큘럼] (0) | 2021.02.17 |