[백준] 2644 - 촌수계산 (파이썬, Python)

https://pixabay.com/ko/photos/우산-햇빛-여자-비-빛-6239364/

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

2644번: 촌수계산

 

그래프 문제입니다.

입력으로 부모-자식 관계가 주어지고 주어진 두 사람의 촌수를 구하는 것이 이 문제의 목표입니다.

 

저는 깊이 우선 탐색(dfs)으로 이 문제를 해결했습니다.

접근 방식

1. 입력으로 주어진 가계도를 2차원 배열에 저장합니다.

2. 촌수를 계산해야 하는 사람을 각각 p1, p2라고 할 때, p1을 시작으로 탐색을 진행합니다.

3. 현재 탐색하는 사람과 관계가 있는 사람(연결된 사람) 중 아직 탐색하지 않은 사람(방문하지 않은 노드)이 있으면 stack에 넣어줍니다.

4. 3번을 반복하면서 만약 p2를 발견한다면 현재까지의 촌수를 반환하고, 탐색이 끝나도 발견하지 못한다면 -1을 반환합니다.

전체 코드

제출 언어: PyPy3

시간: 104ms

import sys

def solution():
    global n, p1, p2, relation
    visited = [ False ] * (n+1)

    stack = [ (p1, 0) ]
    visited[p1] = True

    res = -1

    while stack:
        cp, cd = stack.pop()

        if cp == p2:
            res = cd
            break

        for np in range(n+1):            
            if relation[cp][np] and not visited[np]:
                visited[np] = True
                stack.append((np, cd+1))
    
    return res
        

if __name__ == "__main__":
    n = int(sys.stdin.readline().strip())

    p1, p2 = map(int, sys.stdin.readline().strip().split())

    m = int(sys.stdin.readline().strip())

    relation = [ [ False ] * (n+1) for _ in range(n+1) ]

    for _ in range(m):
        r1, r2 = map(int, sys.stdin.readline().strip().split())

        relation[r1][r2] = True
        relation[r2][r1] = True

    res = solution()

    print(res)

---

읽어 주셔서 감사합니다 :)

틀린 부분이 있다면 댓글로 편히 알려주세요😊