[백준][2178] 미로 탐색

• 문제
  • 2178번: 미로 탐색
• 해설

import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)

N, M = [int(x) for x in sys.stdin.readline().strip().split()]
maze = [list(map(int, x.strip())) for x in sys.stdin.readlines()]

queue = deque()
dx_dy = [(-1, 0), (1, 0), (0, 1), (0, -1)]
went_or_not = [[False for y in range(M)] for x in range(N)]

def can_go(x, y):
    if 0 <= x < N and 0 <= y < M and maze[x][y] and not went_or_not[x][y]:
        return True
    else:
        return False

def is_destination(x, y):
    return x == (N - 1) and y == (M - 1)

ans = [N * M]

def bfs(x, y, cnt):
    went_or_not[x][y] = True
    cnt += 1
    for diff in dx_dy:
        ax, ay = [sum(z) for z in zip((x, y), diff)]
        if can_go(ax, ay):
            went_or_not[ax][ay] = True
            if is_destination(ax, ay):
                ans[0] = ans[0] if ans[0] < cnt else cnt
            else:
                queue.appendleft((ax, ay, cnt))
    if len(queue):
        ax, ay, cnt = queue.pop()
        bfs(ax, ay, cnt)

bfs(0, 0, 1)
print(ans[0])

• 포인트
  • bfs문제