[알고리즘] 촌수계산 - 그래프

문제 링크

촌수계산: https://www.acmicpc.net/problem/2644

 

문제탐색

기본 원리 탐색

• 두 사람의 촌수를 구한다는 것은, 그래프에서 두개 지점의 거리를 구하는 것과 같습니다.
• 단, 친척관계가 없다면 (그래프가 이어져있지 않다면) -1을 출력해야 합니다.

 

시간복잡도와 알고리즘

• 시간제한 : 1초
  • 약 1억번의 연산이 가능하다고 가정합니다.
• 최대 사람 수 : 100  
  • BFS혹은 DFS로 그래프를 탐색할때 시간복잡도는 O(N+M)이며  이 문제는 부모가 1명만 존재하므로  M은 N보다 클수 없는 트리구조를 따르고 있습니다. 그러므로 시간복잡도는 입력을 포함해 O(2N+M) = 300회 미만으로 충분합니다.

 

=> BFS,DFS모두 사용할 수 있지만, 두 지점사이 거리를 구하는 문제(최단거리) 이므로 BFS를 사용하여 트리를 탐색합니다.

 

코드설계하기

 

• 그래프 초기화
  • 입력 데이터를 기반으로 부모-자식 관계를 그래프로 표현합니다.
  • 그래프는 양방향으로 연결된 형태로 저장합니다.
• BFS 탐색 구현
  • BFS를 통해 두 사람 사이의 최단 거리를 탐색합니다.
  • 시작 노드에서부터 연결된 노드를 탐색하며, 방문하지 않은 노드만 탐색 리스트에 추가합니다.
  • 도달한 노드까지의 거리를 기록합니다.
• 결과 반환
  • BFS 탐색 중 목표 노드에 도달하면 그때까지의 거리를 반환합니다.
  • BFS가 종료될 때까지 목표 노드에 도달하지 못하면 -1을 반환합니다.

 

시도회차 수정사항

 

정답코드

from collections import deque
import sys

# BFS로 촌수 계산
def bfs(start, end):
    visited = [-1] * (n + 1)  # 방문 여부 및 촌수 저장 (-1은 미방문)
    queue = deque([start])
    visited[start] = 0  # 시작 노드는 촌수 0

    while queue:
        current = queue.popleft()

        # 목표 노드에 도달하면 촌수 반환
        if current == end:
            return visited[current]

        # 연결된 노드 탐색
        for neighbor in graph[current]:
            if visited[neighbor] == -1:  # 미방문 노드만
                visited[neighbor] = visited[current] + 1
                queue.append(neighbor)

    return -1  # 목표 노드에 도달할 수 없을 때
        
def graph_bfs(n, person1, person2, relationships):
    # 그래프 초기화
    graph = {i: [] for i in range(1, n + 1)}
    for x, y in relationships:
        graph[x].append(y)
        graph[y].append(x)

    return bfs(person1, person2)


# 입력 처리
n = int(sys.stdin.readline())
person1, person2 = map(int, sys.stdin.readline().split())
m = int(inpusys.stdin.readline())
relationships = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]

# 결과 계산 및 출력
result = graph_bfs(n, person1, person2, relationships)
print(result)