[백준/BOJ] - 2644번 python 풀이 - DFS

---

Key Point

1. 함수 dfs의 매개변수를 start 와 count 두개로 설정해두고 노드를 이동할 때 마다 count를 늘려간다.

2. p1 노드와 p2 노드가 만났을 때의 count 값을 출력하면 되는 문제.

3. dfs 특성상 한 방향으로 끝까지 들어갔다가 해당하는 노드가 없을 경우 dfs 재귀함수를 호출할 때마다 count 값을 1씩 늘려가던 것을 이전 dfs로 돌아가며 count 값 을 더했던 것이 이전 상태로 돌아가는 점을 인지해야한다.

4. dfs 함수가 마무리 되려면 재귀함수의 마지막 dfs에서 부터 역방향 (마치 stack 처럼) 으로 진행하게 된다. dfs 함수의 마지막에 visited set 자료형에 담긴 해당 값을 remove 시켜주는 동작을 수행하여 방문처리를 취소한다.

---

import sys
input = sys.stdin.readline
cnt = 0
def dfs(start, count):
    visited.add(start)
    for item in family[start]:
        if start == p2:
            print(count)
            exit(0)
        if item not in visited:
            dfs(item, count+1)

    visited.remove(start)


n = int(input())
p1, p2 = map(int, input().split())
r = int(input())
family = [[]*0 for _ in range(n+1)]
visited = set()
for _ in range(r):
    a, b = map(int, input().split())
    family[a].append(b)
    family[b].append(a)
dfs(p1,cnt)
print(-1)