[Baekjoon] 2644 촌수계산 python

🏷 문제

💡 코드

from collections import deque

n = int(input())
p1, p2 = map(int, input().split())
m = int(input())
graph = [ [] for _ in range(n+1) ]
visited = [ False for _ in range(n+1) ]

def bfs(p1,p2): 
    q = deque()
    q.append([p1,0])
    # 큐가 빌 때 까지 반복
    while q:
        val,cnt = q.popleft()
        # 타겟값이면 리턴
        if val == p2:
            return cnt
        if not visited[val]:
            visited[val] = True
            # 촌수가 같아야 하므로, 인접 노드를 알아보기 전에 카운트를 세어야 함
            cnt += 1
            # 해당 노드의 인접 노드를 하나씩 살펴봄
            for i in graph[val]:
                if not visited[i]:
                    q.append([i,cnt])
    return -1


for i in range(m):
    x, y = map(int, input().split())
    '''
    예) 1 3 을 입력하면, 1 노드에 3을 넣어주고, 3 노드에도 1을 넣어줌
    '''
    graph[x].append(y)
    graph[y].append(x)

print(bfs(p1,p2))

🔑