문제

두 사람의 관계가 주어졌을 때,
이 둘 사이의 촌수(거리)를 계산하는 문제이다.

부모-자식 관계가 주어짐
두 사람 사이의 촌수를 구하기
연결이 안 되어 있으면 -1

💡 문제 접근 : DFS인가 BFS인가?

👉 사람 간 관계 = 그래프
👉 부모-자식 관계 → 양방향 간선

👉 “촌수” = 두 사람 사이의 거리 (간선 개수)
👉 두 노드 사이 거리 찾기 문제

이 문제를 처음봤을때 “최소 거리(촌수)를 찾아야 하니까 BFS?”라고 생각했다.
DFS를 사용한다 하더라도 모든 경로 탐색 + 최솟값 갱신 필요하다고 생각했다.

하지만 실제로는 BFS, DFS로도 충분히 해결 가능하다.
이 문제의 관계는 단순한 그래프가 아니라 트리(Tree) 구조로 볼 수 있다.

부모 - 자식 관계는 트리 구조이다.
즉, start → end로 가는 경로가 딱 하나인 것이다.

트리의 특징

• 사이클이 없음
• 두 노드 사이 경로는 항상 하나

따라서 이 문제는 BFS, DFS 모두 가능하며, DFS로 푼다고 하더라도 굳이 최솟값 갱신하는 과정이 필요없다.

---

BFS 풀이

from collections import deque

n = int(input())
start, end = map(int, input().split())
m = int(input())

graph = [[] for _ in range(n+1)]
visited = [0] * (n+1) 

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

def bfs(v):
    queue = deque()
    queue.append(v)
    visited[v] += 1

    while queue:
        now = queue.popleft()
        if now == end:
            return visited[now] - 1
        for next in graph[now]:
            if not visited[next] :
                visited[next] = visited[now] + 1
                queue.append(next)
    
    return -1

print(bfs(start))

---

DFS 풀이

from collections import deque

n = int(input())
start, end = map(int, input().split())
m = int(input())

graph = [[] for _ in range(n+1)]
visited = [False] * (n+1) 
result = -1

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

def dfs(v, depth):
    global result

    if v == end:
        result = depth
        return 
    
    visited[v] = True

    for next in graph[v]:
        if not visited[next]:
            dfs(next, depth + 1)

dfs(start, 0)

print(result)