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

링크

백준 2644 촌수계산

처음엔 트리를 구현해서 풀려 했는데 생각처럼 잘 되지 않았다.
다른 방법을 찾다 bfs를 구현해서 풀었다.
항상 2차원 bfs를 하다가 1차원을 하려니까 조금 헤맸다.
사실 똑같은건데.. 반성해야겠다.

정답 코드

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

def bfs(start, end):
    q = deque()
    q.append(start)
    while q:
        vs = q.popleft()
        for v in link[vs]:
            if visit[v] == -1:
                visit[v] = visit[vs] + 1
                if v == end:
                    return visit[v]
                q.append(v)
    return -1

n = int(input())
start, end = map(int, input().split())
m = int(input())
link = [[] for _ in range(n + 1)]
visit = [-1] * (n + 1)

for i in range(m):
    p, c = map(int, input().split())
    link[p].append(c)
    link[c].append(p)

visit[start] = 0
print(bfs(start, end))

알게된 것👨‍💻

• 트리가 아니고 bfs래요