백준1389(파이썬) - 케빈 베이컨의 6단계 법칙

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

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

• 이 문제는 처음보고 아 BFS로 풀어야겠다 싶었다. 
• DFS는 여기서 카운트 갯수 때문에 복잡해 질 것 같아서 생각하지 않았다. 근데 대충 코드는 짜보긴 했다.
• 그냥 일반적으로 양방향 노드 그래프를 만들어주고, 일반적인 deque()함수를 이용한 BFS코드를 짰다.
• 그리고 BFS 함수를 한번 실행시킬 때마다, start노드에서 다른 노드로 갈 수 있을 때, num리스트안의 각각 인덱스에 맞는 값을 1씩 더해줘서 다음 BFS함수로 그 값을 넘겨주고 retrun으로 num리스트에 있는 수들의 총합 값을 받아오는 방식을 사용했다.
• 그리고 마지막으로 result 리스트를 만들어주고, 노드 1번부터 n번 까지 훑으면서, 그 결과 값(sum(num))값을 result 리스트안에 넣어준다. 그 이후에는 가장 작은 숫자가 있는 인덱스를 구해주면 된다.
• 첫번째 코드가 BFS, 그리고 두번째 코드가 플로이드 워셜을 이용한 코드이다. 

#bfs문제
import sys
from collections import deque
input = sys.stdin.readline

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)

def bfs(graph,start):
    num = [0] * (n+1)
    q = deque()
    visited[start] = 1
    q.append(start)
    while q:
        a = q.popleft()
        for i in graph[a]:
            if visited[i] == 0:
                num[i] = num[a]+1
                q.append(i)
                visited[i] = 1
    return sum(num)

result = []
for i in range(1,n+1):
    visited = [0 for _ in range(n+1)]
    result.append(bfs(graph,i))
print(result.index(min(result))+1)
##########################################################플로이드워셜
import sys
from collections import deque
input = sys.stdin.readline
Min = 1000000000
n,m = map(int,input().split())
graph = [[0]*n for _ in range(n)]
for _ in range(m):
    a,b = map(int,input().split())
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1

for i in range(n): #거치는점
    for j in range(n): #출발점
        for k in range(n): #도착점
            if j == k:
                continue
            elif graph[j][i] and graph[i][k]:
                if graph[j][k] == 0:
                    graph[j][k] = graph[j][i] + graph[i][k]
                else:
                    graph[j][k] = min(graph[j][k],graph[j][i] + graph[i][k])
for i in range(n):
    result = 0
    for j in range(n):
        result += graph[i][j]
    if Min > result:
        Min = result
        person = i
print(person+1)

#####################################################dfs풀이(실패)
""" def dfs(graph,start,visited,cnt):
    cnt += 1
    for i in graph[start]:
        if visited[i] == 0:
            visited[i] = 1
            print(cnt)
            dfs(graph,i,visited,cnt) """
            

""" answer = [[] for _ in range(n+1)]
for i in range(1,n+1):
    visited = [0 for _ in range(n+1)]
    cnt = 0
    dfs(graph,i,visited,cnt)
    print("---")
    answer[i].append(cnt)
print(answer)
print(graph) """