(백준2644&Python) 재귀식을 사용하는 DFS를 사용할 때 실패 사례에 대한 반환 값을 고려하십시오.

# 문제

# 코드

## 면세점

import sys

n = int(sys.stdin.readline()) # 전체 사람의 수
a,b = map(int,sys.stdin.readline().split()) # 촌수를 계산해야하는 a,b
m = int(sys.stdin.readline()) # 관계의 개수

ddict = ( () * 1 for _ in range(n+1)) # 인접리스트 만들기
visit = (False) * (n+1)

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

def dfs(a,cnt) :

  if a==b :
    return cnt

  re = -1
  for next in ddict(a) :
    if not visit(next) :
      visit(next) = True
      re = max(dfs(next,cnt+1),re)

  return re

visit(a) = True
result = dfs(a,0)
if  result== None :
  print(-1)
else :
  print(result)

## BFS

import sys
from collections import deque

n = int(sys.stdin.readline()) # 전체 사람의 수
a,b = map(int,sys.stdin.readline().split()) # 촌수를 계산해야하는 a,b
m = int(sys.stdin.readline()) # 관계의 개수

ddict = ( () * 1 for _ in range(n+1)) # 인접리스트 만들기
visit = (False) * (n+1)

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

## BFS (성공) ##
## start a, target b
dq = deque()
dq.append((a,0))
visit(a) = True

while len(dq) !
= 0 :
  cur = dq.popleft() # ( 현재값, 카운터 )

  for item in ddict(cur(0)) :
    next = (item, cur(1) + 1)

    if visit(next(0)) == False :
      if next(0) == b :
        print(next(1))
        exit()
      else :
        visit(next(0)) = True # 방문처리
        dq.append(next) # 큐에 넣기

print(-1)

# 해결하다

• 이것은 간단한 인접 목록을 사용하여 쉽게 해결할 수 있습니다.
  
• BFS의 경우 방문 처리 요건을 잘 생각해보면 쉽게 해결된다.
  
• 도수 계산이기 때문에 만나는 지점은 무조건 최단 거리이기 때문에 BFS나 DFS 둘 다 사용 가능하다.
  
• 재귀적 방법으로 DFS를 풀 때 무조건 실패 사례가 충족됩니다.
  이를 고려하지 않고 return dfs()와 같은 방식으로 풀면 오답이 나올 수 있습니다.
  
• DFS에서는 비정상적인 조건(복원..)이 없으면 스택을 생성하여 역추적을 해결해야 합니다.