[파이썬] 백준 2644 : 촌수계산

[파이썬] 백준 2644 : 촌수계산

2644번: 촌수계산 (acmicpc.net)

2644번: 촌수계산

실버 2

그래프, BFS, DFS

---

접근

노드별로 방문처리를 계층적으로 한다.

첫번째 예제에서 7과 3 두 사람의 촌수를 나타내기를 요구했으므로 bfs탐색 시 7을 인수로 주도록 한다.

 

코드 (bfs)

import sys; input = sys.stdin.readline
from collections import deque

def bfs(node):
    queue = deque([node]) # 방문처리를 하고 반복문으로 넘기면 구하려는 값보다 1씩 큰 값으로 방문처리 값이 매겨지므로 그냥 넘긴다.
    while queue:
        v = queue.popleft()
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = visited[v] + 1  # chon1 노드에 대해서 각각의 노드까지의 거리를 방문처리 리스트에 기록한다.

n = int(input())    # 노드 수
chon1, chon2 = map(int, input().split())
m = int(input())    # 간선 수
graph = [[] for _ in range(n+1)]
visited = [0]*(n+1)
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
bfs(chon1)
print(visited[chon2] if visited[chon2] > 0 else -1)