[백준] 2178번: 미로 탐색

💡문제 설명

NxM의 격자를 입력으로 받고, 격자의 좌상단에서 우하단으로 가는 최소 칸 수를 구하는 문제이다.

💡풀이 및 코드

최소 경로 문제이고, 또 미로를 무방향 그래프로 나타낼 수 있기 때문에 자연스럽게 BFS(Breadth first search)를 활용해 풀고자 했다.

from collections import deque

N,M = map(int, input().split())
maze = [list(map(int, input())) for _ in range(N)]
distance = [[0]*M for _ in range(N)]

def bfs(x,y):
    queue = deque()
    distance[x][y] = 1
    queue.append((x,y))
    
    while queue:
        x,y = queue.popleft()

        for dx, dy in [(-1,0), (1,0), (0,-1), (0,1)]:
            nx, ny = x+dx, y+dy

            # 아직 방문 안한, 격자 맵 안에 위치한 노드
            if 0 <= nx < N and 0 <= ny < M and distance[nx][ny]==0: 
                
                if maze[nx][ny] == 1: # 해당 노드의 길이 뚫려있는 경우만
                    queue.append((nx,ny))
                    distance[nx][ny] = distance[x][y]+1

bfs(0,0)
print(distance[N-1][M-1])

풀고 난 후, 다른 사람의 풀이를 살펴보니, 굳이 distance 변수에 칸 수를 기록하지 않아도 된다는 것을 알았다. 따로 변수를 생성하지 않고 maze 변수를 활용해 칸 수를 해당 인덱스에 담으면 된다. 그러면 메모리를 줄일 수 있겠다. 그러나 입력 받은 오리지널 값들을 유지할 필요가 있는 경우에는 따로 변수를 만드는 편이 낫겠다.