DFS 뜯어보기

• https://www.youtube.com/watch?v=qpBUjNSzGX8
• https://editor.p5js.org/talksis/sketches/Zln0cTKY5

📌모범사례 (완전탐색)

• 검은색 : 밟았던 길
• 초록색 : 상하좌우 탐색

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)

무한 루프에 빠진다.