문제

예제 입력 1

9
7 3
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

예제 출력 1

3

예제 입력 2

9
8 6
7
1 2
1 3
2 7
2 8
2 9
4 5
4 6

예제 출력 2

-1

문제 이해

이 문제는 촌수를 구해야 하는 두 사람 중 하나를 main에서 DFS를 호출할때 시작점으로서 넣어주고, DFS함수 안에서 조건문으로 들어오는 값이 나머지 하나의 값이면 카운트 값을 리턴한다.

그래프나 2차원 배열로 탐색을 할때, 카운트가 잘 될지 의심이 들긴 했지만 애초에 visited를 사용하는게 재방문을 방지하기 위함이니까 카운트를 걱정할 필요는 없다.

틀린 코드

# 백준 2644번 촌수계산

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def DFS(idx):
    global graph, visited, cnt, answer
    visited[idx] = True
    cnt += 1
    
    if idx == person2:
        answer = cnt - 1
        return
    
    
    for i in graph[idx]:
        if not visited[i]:
            DFS(i)

# 0. 입력 및 초기화
N = int(input())
person1, person2 = map(int, input().split())
M = int(input())
cnt = 0
# 못 찾으면 -1을 출력하기 위해 초기값 -1
# 만약 DFS에서 찾아지면 cnt 값을 answer에 입력
answer = -1

graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)

# 1. 연결 요소 입력
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

# 2. 오름차순 정렬
for i in range(1, N+1):
    graph[i].sort()

# 3. DFS호출
DFS(person1)

# 4. 출력
print(answer)

틀린 이유는 cnt 때문이다. 사실 정확하게는 왜 틀렸는지 모르겠다. cnt를 전역 대신 매개변수로 바꾸면 정상 작동한다.

cnt로 촌수를 계산하려니까 메인에서 첫호출이 되었을 때는 cnt가 증가되면 안된다. 그런데 깊이 1이상에서는 촌수가 하나씩 증가해야한다. 그래서 cnt에 -1을 했는데도 틀렸다고 한다.

만약 메인에서 DFS 호출을 두 번 이상하면 cnt 값이 이상할 순 있는데 이건 한번 호출인데 왜 틀렸는지 모르겠다. 백준의 24479, 24480번에서는 order의 사용과 별로 차이점이 없어보이는데. 이 문제는 더 고민해 봐야겠다.

일단은 보통 그래프 탐색에서 깊이를 매개변수로 넣는 것을 고려해서 매개변수로 사용한다.

정답 코드

# 백준 2644번 촌수계산

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def DFS(idx, cnt):
    global graph, visited, answer
    visited[idx] = True
    
    if idx == person2:
        answer = cnt
        return
    
    for i in graph[idx]:
        if not visited[i]:
            DFS(i, cnt + 1)

# 0. 입력 및 초기화
N = int(input())
person1, person2 = map(int, input().split())
M = int(input())
cnt = 0
# 못 찾으면 -1을 출력하기 위해 초기값 -1
# 만약 DFS에서 찾아지면 cnt 값을 answer에 입력
answer = -1

graph = [[] for _ in range(N+1)]
visited = [False] * (N+1)

# 1. 연결 요소 입력
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

# 2. 오름차순 정렬
for i in range(1, N+1):
    graph[i].sort()

# 3. DFS호출
DFS(person1, 0)

# 4. 출력
print(answer)