파이썬 | 백준 | 2644 | 촌수계산

solution

1. bfs 이용

2. 입력받은 수가 같으면 0촌

# 2644, 촌수계산
import sys
from collections import deque

def bfs(x, y):
    if x == y:
        return 0
    visited[x-1] = 1
    q = deque()
    q.append(x-1)

    while q:
        tmp = q.popleft()
        for i in fam[tmp]:
            if not visited[i]:
                visited[i] = visited[tmp] + 1
                if i == y-1:
                    return visited[tmp]
                q.append(i)
    return -1


n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())

fam = [[] for _ in range(n)]

m = int(sys.stdin.readline())
for _ in range(m):
    p, c = map(int, sys.stdin.readline().split())
    fam[p-1].append(c-1)
    fam[c-1].append(p-1)

visited = [0] * n
print(bfs(a, b))

31928KB

80ms

 

문제 출처 https://www.acmicpc.net/problem/2644

2644번: 촌수계산