[백준] 미로 탐색(2178) - python

문제 링크 : http://boj.kr/2178

문제 요약

N x M 크기의 배열 미로에서 1은 이동 가능한 칸을 0은 이동 불가능한 칸을 나타냅니다.

(1, 1) 에서 출발해서 (N, M) 까지 이동할 때 지나야 하는 최소 칸을 구하는 문제입니다.

입력

N, M (2 ≤ N, M ≤ 100)

N개의 줄에 M개의 정수로 미로

예시)

2 3
110
011

풀이

현재 칸에서 이동할 수 있는 경로가 정해져 있기 때문에 그래프 구조라고 생각해서 접근해 보았습니다.

각 칸에서는 지나오지 않은 4방향의 칸들 중 이동 가능한 칸으로 이동하는 방법을 생각해서 따라서 그래프 BFS 구조로 구현해 보겠습니다.

import sys
input = sys.stdin.readline

N, M = map(int,input().split())
maze = []
for _ in range(N):
    maze.append(list(map(int,list(input().rstrip()))))

q = [(0,0)] # x,y,칸수
while q:
    nowX, nowY = q.pop(0)
    if nowX == (N-1) and nowY == (M-1):
        print(maze[nowX][nowY])
        break
    
    block = maze[nowX][nowY]
    maze[nowX][nowY] = 0
    dx = [1,0,0,-1]
    dy = [0,1,-1,0]
    for i in range(4):
        nextX = nowX + dx[i]
        nextY = nowY + dy[i]
        if nextX >= 0 and nextX < N and nextY >= 0 and nextY < M:
            if maze[nextX][nextY] == 1:
                q.append((nextX,nextY))
                maze[nextX][nextY] += block

원래 visited 변수를 만들어서 방문 여부를 판단할까 생각했지만 하나의 maze 리스트에서 진행하고자 한 칸에 방문했을 때 그 칸까지의 방문 칸 수를 저장하고 방문한 칸을 0으로 만들어서 재방문하지 못하게 만들어서 풀어보았습니다.

 

기억해야 할 점

q 를 사용하면서 q.pop() 으로 푸는 걸 진행하다가 답이 나오지 않아서 잠시 고민했고, 맨 앞의 값을 빼야하기 때문에 q.pop(0)으로 바꿔주었다.