[백준] 2178번: 미로 탐색

문제

N×M크기의 배열로 표현되는 미로가 있다.

1 0 1 1 1 1
1 0 1 0 1 0
1 0 1 0 1 1
1 1 1 0 1 1
미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

어떻게 풀면 좋을까?

x로 가는 방향 [0, 0, 1, -1]
y로 가는 방향 [1, -1, 0, 0]
내가 이 길을 갈 수 있는지 체크하고, 지나갔던 길이지 여부를 체크한다.

풀이

import math

#아래 위 오른쪽 왼쪽
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

n, m = map(int, input().split())
miro = [list(map(int, input())) for i in range(n)]
bool_miro = [[True] * m for i in range(n)]
bool_miro[0][0] = False
min_count = math.inf

# 계속 호출 될 함수
def dfs(x, y, count):
    # 아예 미로에서 벗어나면
    if x < 0 or y < 0 or x >= n or y >= m:
        return
    # 미로 끝에 도착하면
    if x == n - 1 and y == m - 1:
        global min_count
        if min_count > count:
            min_count = count
            return
    # 미로를 탐방중!
    for i in range(4):
        dir_x = x + dx[i]
        dir_y = y + dy[i]
        # 내가 이 길을 갈 수 있는지 체크한다. 그리고 지나갔던 길인지 여부를 체크한다.
        if dir_x >= n or dir_y >= m:
            continue
        if miro[dir_x][dir_y] == 1 and bool_miro[dir_x][dir_y] == True:
            bool_miro[dir_x][dir_y] = False
            dfs(dir_x, dir_y, count + 1)
            # 갔던 길을 되돌아 오면 다시 True
            bool_miro[dir_x][dir_y] = True
            
dfs(0, 0, 1)
print(min_count)