[파이썬/Python] 백준 2644번: 촌수계산

숨·2024년 7월 21일

코테

알고리즘 문제 풀이

목록 보기

40/105

📌 문제 : 백준 2644번

📌 문제 탐색하기

n : 전체 사람의 수 ( $1 ≤ n ≤ 100$ )
start, end : 촌수 계산하려는 두 사람의 번호
m : 부모 자식들 간 관계의 계수
x, y : 각각 부모, 자식 번호

✅ 입력 조건
1. n 입력
2. 촌수 계산하려는 target 두 사람 번호 입력
3. m 입력
4. m번 반복해 x, y 입력
✅ 출력 조건
1. x, y의 촌수 계산한 정수 출력

1부터 n까지의 번호를 가진 사람들 중에서 알고 싶은 두 사람의 촌수를 계산하는 문제이다.

나를 기준으로,

부모님 → 1촌
조부모님 → 2촌
부모님의 형제자매 → 3촌

위의 예시로 알 수 있다시피, 촌수는 현재 노드에서 찾고자 하는 노드까지 가는데 몇 개의 노드를 이동하면 되는지를 의미한다.

부모님 : 나 → 부모님 ➡️ 1촌,
조부모님 : 나 → 부모님 → 조부모님 ➡️ 2촌,
부모님의 형제자매 : 나 → 부모님 → 조부모님 → 부모님 형제자매 ➡️ 3촌

m번 반복해 입력 받은 x, y는 노드 간 연결 정보를 의미하므로 그래프에 저장한다.

그래프를 순환하며 현재 노드에서 찾고자 하는 번호의 노드를 찾을 때까지 탐색하는 DFS를 아래와 같이 구현한다.

거쳐간 노드를 방문 처리하면서 카운트를 1씩 증가시켜 촌수를 계산한다.
현재 노드가 찾고자 하는 노드 ⭕️ → 그 때까지 계산한 카운트를 출력한다.
현재 노드가 찾고자 하는 노드 ❌ → 재귀적으로 DFS 호출
탐색 종료 후에도 찾지 ❌ → -1 출력

가능한 시간복잡도

그래프 초기화 & 저장 → $O(n + m)$
DFS 탐색 → $O(n + m)$

최종 시간복잡도
$O(n + m)$ 으로 최악의 경우에도 1초 내로 계산이 가능할 것 같다.

알고리즘 선택

입력 받은 두 사람 중 한 사람부터 출발해 다른 한 사람이 나올 때까지 DFS 수행하기

📌 코드 설계하기

DFS 구현
1-1. 방문 처리
1-2. 찾고자 하는 노드 발견 시 촌수 리턴
1-3. 재귀적 탐색
n 입력
찾고자 하는 두 사람 입력
m 입력
그래프 정의
방문 처리 리스트 정의
m 반복해 관계 입력
DFS 수행
결과 출력

📌 시도 회차 수정 사항

1회차

📌 정답 코드

import sys

input = sys.stdin.readline


# DFS 구현
def dfs(v, count):
    # 방문 처리
    visited[v] = 1
    # 찾고자 하는 노드 발견
    if v == end:
        return count
    # 재귀적 탐색
    for i in graph[v]:
        if not visited[i]:
            result = dfs(i, count+1)
            # result가 있다면
            if result is not None:
                return result


# n 입력
n = int(input())

# 찾고자 하는 두 사람 입력
start, end = map(int, input().split())

# m 입력
m = int(input())

# 그래프 정의
graph = [[] for _ in range(n+1)]

# 방문 처리 리스트 정의
visited = [0] * (n+1)

# m 반복해 관계 입력
for _ in range(m):
    parent, child = map(int, input().split())
    graph[parent].append(child)
    graph[child].append(parent)

# DFS 수행
count = dfs(start, 0)

# 결과 출력
if count == None:
    print(-1)
else:
    print(count)