[백준/python] 2644번: 촌수계산

문제

https://www.acmicpc.net/problem/2644

2644번: 촌수계산

---

문제 요약

n명의 부모 자식들 간 관계를 m개 입력 받고, 서로 다른 두 사람의 촌수를 출력한다.

 

+ 기본적으로 부모와 자식 사이를 1촌으로 정의한다.

 

+ 사람들은 1, 2, 3, ... 의 연속된 번호로 각각 표시된다.

 

+ 각 사람의 부모는 최대 한 명만 주어진다.

---

코드

from collections import deque

def bfs():
    queue = deque([a])
    # a 노드부터 bfs 탐색을 위해 큐에 삽입
    check[a] = 0
    # a와 a의 촌수는 0

    while queue:
    # 큐에 요소가 있을 동안 반복
        v = queue.popleft()
        # v는 현재 탐색하는 노드 (큐에서 제거)
        for i in graph[v]:
        # 노드 v가 이동 가능한 노드들 탐색
            if check[i] == -1:
            # 방문하지 않았던 노드라면
                queue.append(i)
                # 큐에 추가
                check[i] = check[v] + 1
                # i의 촌수 저장

n = int(input()) # 전체 사람 수

a, b = map(int, input().split()) # 촌수를 계산할 사람의 번호

m = int(input()) # 부모 자식 관계 수

graph = [[] for _ in range(n + 1)] # graph[0]은 사용 x
# i번 노드가 어느 노드로 이동 가능한지(몇 번과 부모 관계인지) 저장된 graph

# 인접 리스트로 그래프 구현
for i in range(m):
    num1, num2 = map(int, input().split())
    graph[num1].append(num2)
    graph[num2].append(num1)

check = [-1] * (n + 1) # check[0]은 사용 x
# check[i]는 a부터 i까지의 거리 (촌수)

bfs()

print(check[b])

---

코드 설명

1. 촌수를 계산할 사람의 두 사람의 번호를 a, b로 입력 받는다.

 

2. 사람들의 부모 관계를 저장하는 인접 리스트 graph를 생성한다.

 

3. a부터 BFS(넓이 우선 탐색)로 check 배열을 갱신하는 함수 bfs를 정의한다. (큐 이용)

+ check[i]는 a부터 i까지의 촌수를 저장한다. (초기 값: -1)

 

4. check[b]를 출력한다.