[백준 파이썬] 2178번 미로 탐색

2178번 미로 탐색

www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

파이썬 풀이

import sys
import collections
input = sys.stdin.readline

N, M = map(int,input().split())
graph = [[0] * (M) for i in range(N)]
visited = [[0] * (M) for i in range(N)]  # 방문 노드 기록
queue = collections.deque() # 큐
queue.append((0,0)) # 시작 지점
visited[0][0] = 1

dx, dy = [-1,1,0,0], [0,0,-1,1] # x,y 이동 좌표

# 그래프 생성
for i in range(N):
    graph[i] = list(input().rstrip())

# bfs 구현
while queue:
    x,y = queue.popleft() # 큐에서 원소 추출
    if x == N-1 and y == M-1: # 도착 지점에 도달
        print(visited[x][y])

    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if (N-1) >= nx >= 0 and (M-1) >= ny >= 0 and graph[nx][ny] == '1' and visited[nx][ny] == 0:
            queue.append((nx,ny))
            visited[nx][ny] = visited[x][y] + 1 # 경로 갱신