[백준] 촌수계산

문제보기 - https://www.acmicpc.net/problem/2644

문제명    - 촌수계산

난이도    - S2

문제유형 - 그래프이론

풀이일자 - 25.03.18

 

📌 문제 탐색하기

• 가족 관계도가 주어졌을 때, 두 사람 사이의 촌수를 계산하는 문제
• 두 사람 간의 최소 촌수를 구하는 것이 목표
  
  • 사람 수 n (1 ≤ n ≤ 100)
  • 촌수를 계산할 두 사람의 번호
  • 부모-자식 관계의 개수 m
  • 부모 자식간의 관계를 나타내는 두 번호 x,y
• 두 사람 간의 최소 촌수 출력
  • 관계가 없으면 -1 출력

 

🛠 시간복잡도 확인

• 관계가 무방향 그래프이므로 BFS 사용
• n이 최대 100이므로 BFS(너비 우선 탐색) 가능! -> O(N)

 

📌 코드 설계하기

1. BFS를 사용하여 최소 촌수 계산 함수 생성하기
   • 그래프 초기화
     • graph를 딕셔너리 형태로 생성
     • n개의 노드마다 빈 리스트를 추가
   • 무방향 그래프 구축
     
     • a - b 관계를 양방향(a -> b, b -> a)으로 저장
   • 최소 촌수 탐색
     • queue 사용하여 BFS 수행
     • (현재 노드, 촌수) 형태로 큐에 저장
     • 방문한 노드는 visited 집합에 추가하여 중복 방문 방지
   • 노드 탐색 및 촌수 반환
     • y를 찾으면 현재 촌수를 반환
     • 촌수 관계가 없으면 -1 반환
2. n, x,y, m 입력받기
3. 결과 출력

 

📌 정답 코드(1회차)

from collections import deque
import sys

def find_relation(n, x, y, relations):
    # 1. 그래프 초기화
    graph = {}
    for i in range(1, n + 1):
        graph[i] = []
    
    # 2. 무방향 그래프
    for a, b in relations:
        graph[a].append(b)
        graph[b].append(a)

    # 3. 최소 촌수 탐색
    queue = deque([(x, 0)])  # (현재 노드, 촌수)
    visited = set([x])  # 방문한 노드 저장

    while queue:
        current, count = queue.popleft()  # 현재 노드와 촌수 가져오기

        # 4. 목표 노드(y) 찾으면 촌수 반환
        if current == y:
            return count

        # 5. 현재 노드에서 이동할 수 있는 모든 노드 탐색
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, count + 1))

    return -1  # 촌수 관계 없음

n = int(sys.stdin.readline()) 
x, y = map(int, sys.stdin.readline().split()) 
m = int(sys.stdin.readline())
relations = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]

# 결과 출력
print(find_relation(n, x, y, relations))