[DFS][완전 탐색] - 미로탐색

문제

주어진 그래프에서 0,0부터 6,6 에 가는 방법을 모두 구해라

문제 풀이

def DFS(x,y):
    global cnt
    if x == 6 and y == 6:
        cnt +=1
    else:
        for i in range(4):
            nx = x+ dx[i]
            ny = y+ dy[i]
            if 0<=nx<7 and 0<=ny<7 and board[nx][ny] == 0:
                board[nx][ny] = 1
                DFS(nx, ny)
                board[nx][ny] = 0
    


if __name__ == "__main__":
    dx = [0,0,-1,1]
    dy = [1,-1,0,0]

    board=[list(map(int,input().split())) for _ in range(7)]
    cnt = 0
    board[0][0] = 1
    DFS(0,0)

    print(cnt)

• 해당 문제는 거리가 아닌 도착점에 도착할 수 있는 여러 방법에 대해서 물어보는 것이기에 DFS를 사용해 풀 수 있다.
• board[nx][ny] = 1로 바꿔준 것은 해당 노드가 돌 때 중첩해서 가지 못하게 함이다.
• board[nx][ny] = 0으로 다시 바꿔준 것은 해당 노드에 함수가 역할이 끝나면 다시 돌아와 다른 길을 찾아야 할 때 중첩해서 그 길을 이용해 갈 수가 있기 때문이다. 
• 이때 x와 y가 6일 때 cnt를 증가하는 이유는 끝에 닿았기 때문이다. 
• 이때 return을 사용해서 종료조건을 만들지 않은 것은 cnt +1을 증가한 후 자동 종료되기 때문이다. (모든 함수를 끝냈다면 마지막으로 cnt를 증가시키고 끝날 것이다.