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

 

 

 

문제

 

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

 

2644번: 촌수계산

 

첫번째 줄: 전체 사람의 수

둘째 줄: 촌수를 계산해야 하는 서로 다른 두 사람의 번호

셋째 줄: 부모 자식들 간의 관계의 개수

 

 

넷째 줄 부터 부모 자식간의 관계를 나타내는 두 번호 입력

 

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성

 

------------------------------------------------------------------------------------------------------------------

 

풀이

 

def dfs(st, find):
    ST = []
    visited = [0] * (N+1)
    ST.append(st)
    visited[st] = 1

    while ST:
        v = ST.pop()

        for w in G[v]:
            if w == find: return visited[v]

            if visited[w] == 0:
                ST.append(w)
                visited[w] = visited[v] + 1

    return -1

import sys

N = int(sys.stdin.readline()) # 노드 개수
A, B = map(int, sys.stdin.readline().split())
R = int(sys.stdin.readline()) # 엣지의 개수

G = [[] for _ in range(N+1)]
for _ in range(R):
    v1, v2 = map(int, sys.stdin.readline().split())
    G[v1].append(v2)
    G[v2].append(v1)

print(dfs(A, B))