백준 2178번 미로 찾기

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

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