[baekjoon] 백준 2644번(파이썬): 촌수계산

문제

2644번: 촌수계산

- 우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다.

- 이러한 촌수는 다음과 같은 방식으로 계산된다.

- 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다.

- 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

- 여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 문제이다.

- 두 사람의 촌수를 나타내는 정수를 출력한다.

- 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력해야 한다.

알고리즘

- bfs를 통해 문제를 수행한다.

- 촌수를 계산해야 하는 서로 다른 두 사람 중 1명을 기준으로 나머지 1명을 만날 때까지 탐색한다.

- 모든 노드를 탐색하고도 만나지 못한다면 -1을 리턴한다.

- 모든 노드를 탐색 중 만나게 되면 그때의 cnt 값을 리턴한다.

- cnt는 탐색을 할 때마다 카운트한다.

코드

import sys
from collections import deque


# bfs 탐색
def bfs(v, w):
    cnt = 0
    queue = deque([[v, cnt]])
    while queue:
        v, cnt = queue.popleft()

        # 촌수를 계산해야하는 서로 다른 두 사람에 번호가 같아지면 cnt 리턴
        if v == w:
            return cnt

        # 탐색하지 않은 노드라면 탐색하고 카운트
        if not visited[v]:
            cnt += 1
            visited[v] = True

            # 연결된 노드가 탐색하지 않은 노드라면 탐색 리스트에 추가
            for i in result[v]:
                if not visited[i]:
                    queue.append([i, cnt])

    # 모든 노드를 탐색하고도 촌수를 계산해야하는 서로 다른 두 사람에 번호가 같지 않다면 -1 리턴
    return -1


n = int(sys.stdin.readline())
a, b = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())

# 2차원 그래프로 표현
result = [[] for _ in range(n + 1)]
for _ in range(m):
    x, y = map(int, sys.stdin.readline().split())
    result[x].append(y)
    result[y].append(x)

# 탐색 여부
visited = [False] * (n + 1)

# 탐색
print(bfs(a, b))

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법