[백준] 2644 - 촌수계산 [Python(파이썬)]

문제

www.acmicpc.net/problem/2644

풀이

BFS로 풀이했다. 거리(촌수)를 구해야 할 두 노드가 정해져 있기 때문에 시작 노드만 큐에 넣고 탐색을 했다.

코드

import sys, collections

def bfs(start, end):
    q = collections.deque([])
    q.append([start,0])
    visited[start] = 1

    while q:
        cur, cnt = q.popleft()
        if cur == end:
            print(cnt)
            return
        for adj in g[cur]:
            if not visited[adj]:
                visited[adj] = 1
                q.append([adj,cnt+1])

    print(-1)

n = int(sys.stdin.readline().strip())
t1, t2 = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline().strip())

g = collections.defaultdict(list)
visited = [0 for _ in range(n+1)]

for _ in range(m):
    y, x = map(int, sys.stdin.readline().split())
    g[y].append(x)
    g[x].append(y)

bfs(t1, t2)