코드

from collections import deque

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

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

# 최종 결과를 담을 리스트    
answer = []

# 특정 노드와 연결된 모든 노드를 순회해야 하므로 BFS 사용
def bfs(graph, v, visited):
    q = deque()
    
    q.append(v)
    
    visited[v] = 1
    
    while q:
        node = q.popleft()
        
        for i in graph[node]:
            if not visited[i]:
                
                # 마지막 노드까지 간선의 이동 횟수를 계산해야 하므로
                # 한 번 이동할 때 마다 도착한 간선의 visited 값을
                # 이전 간선까지의 이동 횟수 + 1로 표현
                visited[i] = visited[node]+1
                q.append(i)
                
    return sum(visited)

    
for i in range(1, n+1):
    # 각 노드 별 간선의 누적 합을 구해야하므로
    # 노드마다 visited 리스트가 0으로 초기화 돼있어야 함
    visited = [0] * (n+1)
    answer.append(bfs(graph, i, visited))
    
print(answer.index(min(result)) + 1)

문제 해설

케빈베이컨

BFS를 활용하여 푸는 문제이다. 아직 BFS와 DFS를 사용하는 경우를 명확하게 구분하지 못해서 그런지 대뜸 문제를 DFS 풀다가 실패했다… ㅠㅠ 그러다 미로찾기 문제와 유사하다는 것을 느끼고 BFS로 수정하여 푸니 정답으로 인정 받았다.

문제의 요구 사항이 최소 이동 횟수의 값을 구하라는 것이 아닌 그 값을 가지고 있는 사람(노드)을 구하면 되는 것이라 visited 리스트에 이동 횟수를 누적하여 저장하고 노드 별 그 합을 answer 리스트에 담아 그 중 최솟값을 가진 인덱스를 구하면 정답으로 인정된다. 하지만, 위의 그림처럼 누적 합이 직접 수작업으로 세어 보는 것과 값이 다른 것을 알 수 있는데, 만약 문제의 정답이 최소 이동 횟수의 값 자체라면 누적 합에 노드의 개수를 빼주면 정답으로 인정된다. (시작 노드의 이동 횟수를 1로 보고 시작하였으므로 노드 개수마다 1씩 더 많이 이동 횟수가 누적되었으므로 노드의 개수만큼 뺴주면 된다.)

댓글남기기

참고