2644 촌수계산 / DFS, BFS

 

정답

• 어제 풀었던 케빈 베이컨의 법칙과 동일
• 시작 노드로부터 도착노드까지의 거리를 구해서 반환하면 됨

from collections import deque

def BFS (graph, start, n, goal):
    queue = deque()
    queue.append(start)
    visited = [False] * (n + 1)
    visited[start] = True
    distance = [0] * (n + 1)

    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if visited[neighbor] is False:
                distance[neighbor] = distance[current] + 1
                queue.append(neighbor)
                visited[neighbor] = True

                # 방문한 노드가 목표 노드라면 시작점노드로부터의 거리 반환
                if neighbor == goal:
                    return distance[neighbor]

    # 목표 노드에 방문하지 않았다면 -1 함수가 모두 종료되고 -1 반환
    return -1

n = int(input()) # 전체 사람의 수 (노드 수)
x, y = map(int, input().split()) # 촌수를 계산해야 하는 서로 다른 두 사람의 번호
m = int(input()) # 부모, 자식간의 관계의 수 (간선 수)
con = []
for _ in range(m):
    a, b = map(int, input().split())
    con.append((a, b))

graph = []
for _ in range(n + 1):
    graph.append([])

for a, b in con:
    graph[a].append(b)
    graph[b].append(a)

print(BFS(graph, x, n, y))