[백준2644&파이썬] 재귀식을 이용한 DFS 사용할때는 실패케이스에 대한 반환값을 생각하자

# 문제

2644번: 촌수계산

# 코드

## 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에서 백트래킹을 특이한 조건( 원복을 시켜야하는..)이 없다면 스택 만들어서 풀던가 해야겠다.