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

- 문제 : https://www.acmicpc.net/problem/1389

 

문제에 대한 이해도도 부족했고, 풀이도 그렇고 아무튼 부족했던 문제다. 

Silver Level1문제 

 

문제 이해한 거로는 각 번호에서 1번부터 n번까지의 사람들(자기 자신 포함해도 상관없음)과의 깊이를 모두 합한 값을 비교해서 

그 중에서 가장 작은 값을 가진 사람의 번호를 출력하는 것이다 

그럼 1명에 대해서 모든 사람들에 대한 bfs를 해야한다고 생각했다 

그래서 이중 for문을 작성하는 걸로 생각했는데, 그렇게 하면 안됐고 한번의 bfs(v)를 돌려서 v에 대한 각 사람들과의 깊이를 num리스트에 저장한 후 num의 총합을 비교하면 된다 

 

from collections import deque

n,m=map(int,input().split())

data=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)

def bfs(v):
    visit[v]=1
    queue=deque()
    queue.append(v)
    num=[0]*(n+1)
    while queue:
        k=queue.popleft()
        for i in data[k]:
            if not visit[i]:
                num[i]=num[k]+1
                visit[i]=1
                queue.append(i)
    return sum(num)               
          
result=[10**6]*(n+1) 
for i in range(1,n+1):
    visit=[0]*(n+1)
    result[i]=bfs(i)
    
    
final=[]
for i in range(1,n+1):
    if result[i]==min(result):
        final.append(i)
print(min(final))

 

-시도했던 풀이 : 

이렇게 하면 같은 깊이라도 count값이 달라져서 틀린 답을 출력하게 된다 

from collections import deque

n,m=map(int,input().split())

data=[[] for _ in range(n+1)]
for _ in range(m):
    a,b=map(int,input().split())
    data[a].append(b)
    data[b].append(a)

def bfs(v,x):
    visit[v]=1
    queue=deque()
    queue.append(v)
    count=0
    while queue:
        k=queue.popleft()
        if k==x:
            return count
        for i in data[k]:
            if not visit[i]:
                visit[i]=1
                queue.append(i)
                count+=1
result=[0]*(n+1) 
answer=0
for i in range(1,n+1):
    for j in range(1,n+1):
        visit=[0]*(n+1)
        answer+=bfs(i,j)
    result[i]=answer
    answer=0
    
print(result.index(min(result)))