백준/ Silver 1 문제 , 백준 파이썬 1389, 케빈 베이컨의 6단계 법칙 [BFS]

백준/ Silver 1 문제 , 백준 파이썬 1389, 케빈 베이컨의 6단계 법칙 [BFS]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>

 

문제 출처

https://www.acmicpc.net/problem/1389

1389번: 케빈 베이컨의 6단계 법칙

 

 

 

 

 

접근법

 

그래프에 양방향으로 넣어준 뒤 bfs에 그래프랑 입력받은 N을 넣어 호출.

 

이후 1부터 N을 돌면서 각 숫자가 다른 숫자들과 최소한으로 연결된 수를 찾는다.

 

for 문을 한번 돌면 연결된 숫자들을 합하고 최소인지 확인.

 

 

 

풀이

 

 

우선 N과 M을 입력 받는다.

 

이후, N+1 만큼의 배열을 가진 배열을 선언

 

친구관계가 주어지면 양방향으로 입력시켜준다.

 

bfs를 선언, return 값을 바로 출력시켜줄 것이기 때문에 print와 같이 호출한다.

 

 

최소의 값을 찾을 것이기때문에 여유있게 MIN을 maxsize로 선언

 

for 문을 1부터 N까지 모두 확인하기 위해 1~N+1 까지 선언한다

 

for 문을 한번 돌때마다 dq, check, n 을 모두 초기화 시켜주기 위해 내부에 선언한 뒤 

 

dq에 현재 for 문 값을 전달한 뒤 while 문을 통해 dq를 돌린다.

 

현재 입력된 칸에 있는 숫자들을 dq에 차례로 넣어가면서 거리를 계산해주고 

 

다 계산 된 전체의 값을 sum 으로 구해 MIN 보다 작은 값인지 비교해준다.

 

이때 cnt 변수에는 현재 for 문 순서에 해당하는 값을 넣어주고

 

최종적으로 이 숫자를 리턴 시켜주면 된다. (sum 값이 가장 작은 index)

 

 

 

 

 

 

 

정답

 

 

 

import sys
input=sys.stdin.readline
from collections import deque

def bfs(graph,num):
    dq=deque()
    dq.append(num)
    check=[num]
    n=[0]*(N+1)
    while dq:
        x=dq.popleft()
        for i in graph[x]:
            if i not in check:
                n[i]=n[x]+1
                check.append(i)
                dq.append(i)
    return sum(n)
    

N,M=map(int,input().split())
graph=[[] for _ in range(N+1)]
for i in range(M):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

MIN=sys.maxsize
cnt=0
for i in range(1,N+1):
    result=bfs(graph,i)
    if result < MIN:
        MIN=result
        cnt=i

print(cnt)