[알고리즘]백준 2178번 미로 찾기

DFS의 대표격 문제임에도 불구하고 가끔 풀때마다 틀리거나 오래 걸리는 경우가 많아서
확실히 정리하기 위해 코드와 개념을 다시 적어야겠다 생각해서 적어봤습니다.

전체코드

from collections import deque

n, m = map(int, input().split())

mat=[]
for i in range(n):
    mat.append(list(map(int, input())))
x_move = [1, -1, 0, 0]
y_move = [0, 0, 1, -1]


def maze(x, y):
    queue=deque()
    queue.append([x, y])
    mat[x][y]=0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            next_x, next_y = x + x_move[i], y + y_move[i]
            if next_x < 0 or next_x >n-1 or next_y < 0 or next_y > m-1:
                continue
            elif mat[next_x][next_y] == 0:
                continue
            elif mat[next_x][next_y] == 1:
                mat[next_x][next_y] = mat[x][y]+1
                queue.append([next_x, next_y])
            if next_x == n-1 and next_y == m-1:
                return mat[x][y]+2

result = maze(0, 0)
print(result)

한칸씩 이동하며 공간을 체크하는 코드는 위 형태가 가장 대중적인것 같습니다.
기초적인 dfs문제이기 때문에 이에 대해 따로 알아보진 않았으며 주의해서 볼 부분은

x_move = [1, -1, 0, 0]
y_move = [0, 0, 1, -1]



for i in range(4):
            next_x, next_y = x + x_move[i], y + y_move[i]
            if next_x < 0 or next_x >n-1 or next_y < 0 or next_y > m-1:
                continue
            elif mat[next_x][next_y] == 0:
                continue
            elif mat[next_x][next_y] == 1:
                mat[next_x][next_y] = mat[x][y]+1
                queue.append([next_x, next_y])
            if next_x == n-1 and next_y == m-1:
                return mat[x][y]+2

이 두 부분을 이용하여 공간에 대한 탐색을 구현하는 것인데
파이썬에 익숙지 않다면 구현이 상당히 어려울 수 있습니다.
솔직히 말해서 계속해서 문제를 풀면서 익숙해지지 않는 이상 형태를 완벽히 암기하는게 가장 좋아보입니다.