백준 / 촌수계산 / 2644번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 촌수계산 / 2644번 (실버 2단계)

문제 사이트: https://www.acmicpc.net/problem/2644

 

문제 설명

---

나의 풀이

from collections import deque


def solution(graph, n, start, end):
    dq = deque([(start, 0)])

    # 한 번 방문했던 친척은 재방문하지 않는다.
    visited = [False] * (n + 1)
    visited[start] = True

    while dq:
        relative, count = dq.popleft()

        if relative == end:
            return count

        # 다른 친척을 찾는다.
        for i in graph[relative]:
            if not visited[i]:
                dq.append((i, count + 1))
                visited[i] = True

    # 결과가 없다면 -1를 출력
    return -1


def main():
    n = int(input())  # 전체사람의 수

    a, b = map(int, input().split())  # 촌수를 계산해야하는 사람

    m = int(input())  # 부모 자식의 관계 수

    graph = {i: [] for i in range(1, n + 1)}

    for _ in range(m):
        x, y = map(int, input().split())
        graph[x].append(y)
        graph[y].append(x)

    print(solution(graph, n, a, b))


if __name__=="__main__":
    main()

---

※ 알아야 할 것

탐색 알고리즘을 이용해서 문제를 해결 하시면 됩니다.

graph는 딕셔너리로 저장하는게 관리하기 좋습니다.