[백준 2644번] 촌수계산 (python, dfs)

www.acmicpc.net/problem/2644

2644번: 촌수계산

리스트 형태로 이어져있는 노드에 대한 정보를 다 놓고 visited 배열을 이용해 방문한 적 없는 노드들과 다 연결시킨다.

dfs를 돌려도 다 연결이 안되었다면 서로 이어져있지 않는 관계이다.

 

import sys
from collections import defaultdict
from collections import deque

input=sys.stdin.readline

def dfs(a,b):
    q=deque()
    q.append((a,0))
    while q:
        cur,dis=q.popleft()
        if cur==b:
            return dis
        for next in dict[cur]:
            if next==a:
                continue
            if vis[next]: continue
            vis[next]=1
            q.append((next,dis+1))

    return -1



n=int(input())
a,b=map(int,input().split())
dict=defaultdict(list);
m=int(input())
for _ in range(m):
    x,y=map(int,input().split()) #x는 y의 부모
    dict[x].append(y)
    dict[y].append(x)

vis=[0 for _ in range(n+1)]

print(dfs(a,b))