케빈 베이컨의 6단계 법칙

내논리로 2가 나와야하는데 아무리해도 4가나옴/....


def dfs(start,end):
    visited = [0]*(N+1)
    visited[start] = 1
    stack = [start]
    cnt = 0
    while stack:
        t = stack[-1]
        if t == end:
            return cnt
        for i in adj[t]:
            if visited[i] == 0:
                stack.append(i)
                visited[i] = 1
                cnt += 1
                break
        else:
            stack.pop()


N, M = map(int,input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    f1,f2 = map(int,input().split())
    adj[f1].append(f2)
    adj[f2].append(f1)
print(dfs(1,2))

bfs로하니까 바로 2나옴 => 최단거리는 bfs가 답

def bfs(start,end):
    visited = [0]*(N+1)
    queue = [start]
    while queue:
        t = queue.pop(0)
        if t == end:
            return visited[t]
        for i in adj[t]:
            if visited[i] == 0:
                queue.append(i)
                visited[i] = visited[t] + 1

N, M = map(int,input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    f1,f2 = map(int,input().split())
    adj[f1].append(f2)
    adj[f2].append(f1)


print(bfs(1,2))

 

이게 해결되니 문제는 금방풀림..

def bfs(start,end):
    visited = [0]*(N+1)
    queue = [start]
    while queue:
        t = queue.pop(0)
        if t == end:
            return visited[t]
        for i in adj[t]:
            if visited[i] == 0:
                queue.append(i)
                visited[i] = visited[t] + 1

N, M = map(int,input().split())
adj = [[] for _ in range(N+1)]
for _ in range(M):
    f1,f2 = map(int,input().split())
    adj[f1].append(f2)
    adj[f2].append(f1)

result = [500000] + ([0]*N)
for i in range(1,N+1):
    lst = []
    for j in range(1,N+1):
        if i == j:
            continue
        lst.append(bfs(i,j))
    result[i] = sum(lst)
# print(result)
#[500000, 6, 8, 5, 5, 8]
answer = min(result)
print(result.index(answer))

 

1. 1을 기준으로 2,3,4,5까지의 최단거리를 lst에 담고 최종배열result의 인덱스, 즉 1번이면 result[1] 에 각각의 최단거리의 합을 넣는다

2. result에서 가장 적은 값의 인덱스가 구하려는답