[백준] 2644 촌수계산 Python

[백준] 2644 촌수계산 Python

그래프 탐색 문제이다. a,b가 주어졌을 때, 그 관계를 따져서 얼만큼 사다리를 거쳐서 갔는지를 계산하면 된다.
문제는, a와 나머지 관계들에 대한 정보를 어떻게 저장해놓을까 고민했는데, 다행히 a와 b에 대한 관계를 문제에서 물어보고 있기에 a에 대한 촌수 관계 리스트를 선언하고, 그 정보를 바탕으로 계산하는 방식으로 코드를 짰다.

DFS와 BFS 모두 짜도 되지만, 개인적으로는 DFS가 더 빠르지 않을까 싶다.

from collections import deque
import sys
sys.stdin=open("input.txt")

#나 자신은 0촌, 부모 자식 1촌, 나와 할아버지는 2촌

n=int(input()) #전체 사람 수
x,y=map(int,input().split())  #x가 부모, y가 자식
graph=[[]for _ in range(n+1)]
m=int(input()) #관계 수
for _ in range(m):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
visited=[-1 for _ in range(n+1)]

def bfs(graph,x,y):
    q=deque()
    q.append(x)
    visited[x]=0

    while q:
        v=q.popleft()
        if v==y:
            return visited[y]

        for i in graph[v]:
            if visited[i]==-1:
                visited[i]=visited[v]+1
                q.append(i)

    return -1

visited[x]=0

def dfs(graph,x,y):
    if x==y:
        print(visited[y])
        exit()
        return

    for i in graph[x]:
        if visited[i]==-1:
            visited[i]=visited[x]+1
            dfs(graph,i,y)


#print(bfs(graph,x,y))
dfs(graph,x,y)
print(-1)