[Python][백준/BOJ] 2178번 : 미로탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

내 코드

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
board = [list(map(int, input().rstrip())) for i in range(n)]
#최소의 칸 수 = bfs, queue
q = deque([(0,0)])
dx = [1,-1,0,0]
dy = [0,0,1,-1]
while q:
    y,x=q.popleft()
    for i in range(4):
        nx = dx[i]+x
        ny = dy[i]+y
        if 0<=nx <m and 0<=ny < n and board[ny][nx]==1:
            board[ny][nx] = board[y][x] +1
            q.append([ny,nx])
            
print(board[n-1][m-1])

 

BFS

최소의 칸 수를 구하기 때문에 BFS로 푼다. → BFS이므로 queue를 사용한다. → 시간 복잡도를 줄이기 위해 deque을 사용한다.

이렇게 흐름이 이어져서 덱을 사용했다. 

dx = [1,-1,0,0]
dy = [0,0,1,-1]

장소이동이 필요한 문제이므로 이렇게 설정해주었다.

if 0<=nx <m and 0<=ny < n and board[ny][nx]==1:
            board[ny][nx] = board[y][x] +1
            q.append([ny,nx])

그리고 지금까지는 if문을 통해 만약 조건을 벗어나면(벽을 만나거나,,,) break 로 그 상황을 벗어났는데, 이번 문제부터 if문에 조건에 해당될 때만 board가 1인지 확인하기로 했다.

그리고 이건 몇 칸을 가야하는 것인지 세야하므로 아예 board에 칸 수를 세줬다. 그리고 다시 덱에 넣어주고, 덱을 다 돌 동안 추가해주고 빼주기를 반복한다.