BOJ - 2644

백준 문제 링크
촌수계산

❓접근법

1. BFS를 사용했다.
2. 시작 값을 BFS에 넣고, 다른 노드에 방문할 때마다 + 1 해준다.
3. 처음 7부터 시작한다면,
   7은 2와 가족이므로
   answer[2] = answer[7] + 1 = 1(1촌, 부모와 자식)
   그다음 2에서 시작한다면,
   2는 1,7,8,9와 가족이므로
   answer[1] = answer[2] + 1 = 2(7과 1은 조부모)
   answer[8] = answer[2] + 1 = 2(7과 8은 형제)
   answer[9] = answer[2] + 1 = 2(7과 9는 형제)
4. answer에서 비교 대상의 인덱스 값이 0이면 -1을, 아니면 값을 그대로 출력!

👌🏻코드

from collections import deque

N = int(input())

A,B = map(int, input().split())

lst = [[] for _ in range(N+1)]

for _ in range(int(input())):
    x,y = map(int, input().split())
    lst[x].append(y)
    lst[y].append(x)   
    
visited = [False] * (N+1)
answer = [0] * (N+1)

def bfs(v):
    queue = deque()
    queue.append(v)
    
    while queue:
        x = queue.popleft()
        
        for i in lst[x]:
            if not visited[i]:
                visited[i] = True
                answer[i] = answer[x] + 1
                queue.append(i)
bfs(A)

if answer[B] == 0:
    print(-1)
else:
    print(answer[B])