[백준 2178] 미로 탐색(pyhton)

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

문제이해

(0.0)부터 시작하여 (N,M)까지의 도달 거리중 가장 짧은 거리를 return

문제 포인트

bfs로 문제 해결

1. (x,y) 좌표를 기준으로 방문한 곳은 제외하면서 탐색
2. 탐색한 좌표 기준으로 cnt에 +1

제출 코드

import sys
from collections import deque

col, row = map(int, input().split())

graph = [list(map(int, sys.stdin.readline().strip())) for _ in range(col)]

visited = [[False] * row for _ in range(col)]
queue = deque()
queue.append((0, 0, 1))
visited[0][0] = True

while queue:
    cur_y, cur_x, cur_cnt = queue.popleft()


    if cur_y == col - 1 and cur_x == row - 1:
        print(cur_cnt)
        break

    # 상하좌우 방향
    ny = [-1, 1, 0, 0]
    nx = [0, 0, -1, 1]
    for i in range(4):
        next_y = cur_y + ny[i]
        next_x = cur_x + nx[i]

        if 0 <= next_x < row and 0 <= next_y < col:
            if not visited[next_y][next_x] and graph[next_y][next_x] == 1:
                visited[next_y][next_x] = True
                queue.append((next_y, next_x, cur_cnt + 1))

문제가 비슷비슷한 느낌인데 다른 유형의 문제도 풀어봐야 될 듯 하다.