BOJ 2644 촌수계산

https://www.acmicpc.net/problem/2644
시간 1초, 메모리 128MB
input :

• 전체 사람의 수 n
• 서로 다른 두 사람의 번호
• 부모 자식들 간의 관계의 개수 m
• 부모 자식간의 관계를 나타내는 두 번호 x, y(x는 뒤에 나오는 정수 y의 부모 번호)

output :

• 두 사람의 촌수를 나타내는 정수를 출력
• 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이때에는 -1을 출력

---

각 탐색을 할 때 현재 몇번째인지를 기록하기 위한 변수를 가지고 있으면 촌수를 기록할 수 있다.

그리고 체크를 편하게 하려고 양방향 그래프로 생각을 했다.
어차피 visit으로 체크를 할 거니까 상관이 없다.

import sys
sys.setrecursionlimit(10000)

def dfs(now, cnt):
    global ans
    if now == target_two:
        ans = cnt
        return

    for next_node in graph[now]:
        if visit[next_node] == 0:
            visit[next_node] = 1
            dfs(next_node, cnt + 1)

n = int(sys.stdin.readline())
target_one, target_two = map(int, sys.stdin.readline().split())
m = int(sys.stdin.readline())
graph = [[] for i in range(n + 1)]

for i in range(m):
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    graph[y].append(x)

visit = [0] * (n + 1)
ans = -1
dfs(target_one, 0)

print(ans)

입력 데이터 자체가 작아서 그런지 리커젼 리밋을 걸지 않아도 통과했다.