[파이썬 알고리즘 문제풀이] - Section7 / 깊이/넓이 우선 탐색(DFS, BFS) 활용 - 10

미로탐색(DFS)

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요. 출발점은 격자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면

위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.

▣ 입력설명
7*7 격자판의 정보가 주어집니다.

▣ 출력설명
첫 번째 줄에 경로의 가지수를 출력한다.

▣ 입력예제 1
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 0 0 0 1
1 1 0 1 1 0 0
1 0 0 0 0 0 0

▣ 출력예제 1
8

import sys
# sys.stdin = open("input.text", "rt")
from collections import deque

g = [list(map(int, input().split())) for _ in range(7)]
#0으로만 이동해야함.

dq = deque()
dis = [[0] * 7 for _ in range(7)]
dq.append((0,0)) #시작위치 삽입하고 시작
g[0][0] = 1 #시작점 방문 표시 후 시작
dx = [1,-1,0,0]
dy = [0,0,1,-1]

cnt = 0

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:  #경계선 안에 있는지 확인.
                if g[nx][ny] == 0: #방문 전
                    g[nx][ny] = 1
                    DFS(nx,ny)
                    g[nx][ny] = 0 #백트랙킹 시 원상복구

g[0][0] = 1 #시작점은 방문처리.
DFS(0,0)
print(cnt)    

코멘트

이 문제는 출발점에서 도착점까지 갈 수 있는 방법의 수를 구하는 문제야. 방법의 수는 DFS로 현재 위치에서 상하좌우를 살피면서 갈 수 있는 방법을 찾으면 돼

• 즉 경로의 수는 DFS로 풀어도 돼
• 백트랙킹 시 원상복구 잊지말 것.