재귀응용1 --- 미로찾기 with Python

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

보통의 미로탐색의 경우 

아래 코드와 같이 BFS(너비우선탐색, 아직 모른다 하더라도)를 사용하여 푸는데 

검색가능 노드를 찾아 가능한 노드를  q에 쌓으며

해당 q의 유무에 따라  while문을 반복하여 움직인다. 

 

from collections import deque

N, M = map(int, input().split())

graph = []

for _ in range(N):
  graph.append(list(map(int, input())))

def bfs(x, y):
  # 이동할 네 가지 방향 정의 (상, 하, 좌, 우)
  dx = [-1, 1, 0, 0] 
  dy = [0, 0, -1, 1]

  # deque 생성
  queue = deque()
  queue.append((x, y))

  while queue:
    x, y = queue.popleft()
    
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if nx < 0 or nx >= N or ny < 0 or ny >= M:
        continue
  
      if graph[nx][ny] == 0:
        continue
      
      if graph[nx][ny] == 1:
        graph[nx][ny] = graph[x][y] + 1
        queue.append((nx, ny))
  
  return graph[N-1][M-1]

print(bfs(0, 0))

그러나 우리가 이전에 배웠던 것은 for while 같은 반복문은 재귀를 통해 구현할 수 있기에  해당 while 문을 바꿀 수 있다. 

def recursiveBFS(graph, q, discovered):
    if not q:
        return
        
    v = q.popleft()
    print(v, end=' ')
 
    for u in graph.adjList[v]:
        if not discovered[u]:.
            discovered[u] = True
            q.append(u)

    recursiveBFS(graph, q, discovered)