📌모범사례 (완전탐색)
- 검은색 : 밟았던 길
- 초록색 : 상하좌우 탐색
route = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1],
[1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1],
[1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1],
[1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1],
[1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
]
s = len(route)
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
def dfs(x, y):
if route[x][y] != 0:
return
if [x, y] == [s - 1, s - 1]:
return
route[x][y] = 2 # 밟은 위치는 다시 방문 하지 않도록
for i in range(4):
dfs(x + dx[i], y + dy[i])
route[x][y] = 0 # 밟았던 길을 원래대로 복구 (다른 재귀에서 방해받지 않기 위해서)
dfs(1, 1)📌상하좌우 움직일 때마다 길을 밟고 복구하는 경우
모범사례 (완전탐색)와 동일하다
def dfs(x, y):
if route[x][y] != 0:
return
if [x, y] == [s - 1, s - 1]:
return
for i in range(4):
route[x][y] = 2 # 밟은 위치는 다시 방문 하지 않도록
dfs(x + dx[i], y + dy[i])
route[x][y] = 0 # 밟았던 길을 원래대로 복구 (다른 재귀에서 방해받지 않기 위해서)
dfs(1, 1)📌목적지에 도착하면 dfs를 멈추는 경우
finish = False
def dfs(x, y):
global finish
if finish:
return
if route[x][y] != 0:
return
if [x, y] == [s - 1, s - 1]:
finish = True
return
route[x][y] = 2 # 밟은 위치는 다시 방문 하지 않도록
for i in range(4):
dfs(x + dx[i], y + dy[i])
route[x][y] = 0 # 밟았던 길을 원래대로 복구 (다른 재귀에서 방해받지 않기 위해서)
dfs(1, 1)목적지에 도착하면 더이상 dfs를 수행하지 않기 때문에 stack에 새로운 함수가 쌓이지 않는다.
결국 stack에 존재하는 모든 함수들이 pop되면서 탐색이 종료된다.
📌밟았던 길 복구하지 않을 경우
def dfs(x, y):
if route[x][y] != 0: # 빈칸이 아니면 탐색을 멈춘다
return
if [x, y] == [s - 1, s - 1]:
return
route[x][y] = 2 # 밟은 위치는 다시 방문 하지 않도록
for i in range(4):
dfs(x + dx[i], y + dy[i])
# route[x][y] = 0 # 밟았던 길을 원래대로 복구 (다른 재귀에서 방해받지 않기 위해서)
dfs(1, 1)하나의 case를 모두 탐색하고 나서 밟았던 길을 복구하지 않으면,
다음 case를 탐색할 때 이전 case에서 밟았던 길을 탐색하지 않는다(if route[x][y] != 0:)
📌밟았던 길을 체크하지 않을 경우
def dfs(x, y):
if route[x][y] != 0: # 빈칸이 아니면 탐색을 멈춘다
return
if [x, y] == [s - 1, s - 1]:
return
# route[x][y] = 2 # 밟은 위치는 다시 방문 하지 않도록
for i in range(4):
dfs(x + dx[i], y + dy[i])
# route[x][y] = 0 # 밟았던 길을 원래대로 복구 (다른 재귀에서 방해받지 않기 위해서)
dfs(1, 1)무한 루프에 빠진다.
