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

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

2178번: 미로 탐색

 

 

# 조건

• NxM 크기의 배열로 표현되는 미로
• 1은 이동할 수 있는 칸, 0은 이동할 수 없는 칸
• (1,1) 에서 출발하여 (N,M)의 위치로 이동할 때 지나야 하는 최소 칸 수를 출력

 

# 접근 방법

• BFS를 통하여 탐색을 진행한다.
• Queue에 넣어주며 방문기록을 현재 좌표+1로 해준다.
• 간선의 가중치가 모두 같은 그래프로 생각할 수 있기 때문에 bfs를 이용한다면 최단 경로를 바로 구할 수 있다.

 

 

import sys  
sys.setrecursionlimit(10**6)  
sys.stdin = open('input.txt')  
from collections import deque  
  
# 시작 위치  
def bfs(x,y):  
    global visited  
    q = deque()  
    q.append((x,y))  
    visited[x][y] = 1  
    while q:  
  
        sti, stj = q.popleft()  
        for i in range(4):  
            # 탐색 가능한 길 찾아주며 이동 칸 수 기록해주기  
            ni, nj = di[i] + sti, dj[i] + stj  
            if 0<=ni<N and 0<=nj<M and visited[ni][nj] == 0 and maze[ni][nj] == '1':  
  
                visited[ni][nj] = visited[sti][stj] +1  
                q.append((ni,nj))  
  
  
N, M = map(int, input().split())  
  
maze = [list(input()) for _ in range(N)]  
# 탐색 델타 함수  
# 상하좌우  
di, dj = [-1,1,0,0],[0,0,-1,1]  
visited = [[0]*M for _ in range(N)]  
  
  
bfs(0,0)  
  
print(visited[N-1][M-1])