[Baekjoon] 2644 촌수계산

풀이

bfs로 구현했다.
bfs를 구현할때 그냥 외울 것: 넣기 전에 방문 처리하기

입력

문제에서 graph는 무향 그래프이므로, x값에 y, y값에 x를 append

bfs

매개변수로 받은 a를 queue에 넣고 while queue:를 통해 반복문을 돈다.

 

만약 queue에서 나온 값이 b와 같으면 종료return 0

 

for문을 통해 graphx[x]리스트값을 돌며
아직 방문을 하지 않은 값이라면(visited == 0:)
visited 값에 이전 visited값 +1(방문처리)을 해주고 queue.append()

 

만약 사촌관계가 없다면 visited[b]=0이므로 -1이 출력된다.

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

n = int(input().rstrip()) # 전체 사람 수 
a, b = map(int, input().split())# 촌수를 계산해야 하는 두 사람의 번호 
m = int(input())# 부모와 자식들 간의 관계 개수

graph = [[]for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

for i in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)


def bfs(a):
    queue = deque([])
    visited[a] = 1
    queue.append(a)
    while queue:
        x = queue.popleft()
        if x == b: 
            return 0 
        for i in graph[x]:
            if visited[i] == 0: 
                visited[i] += visited[x] + 1
                queue.append(i)

bfs(a)
print(visited[b]-1)