[BOJ] 2178. 미로탐색(python)

📌문제

💪아이디어

1. 맵 만들기
   좌표가 1,1부터 시작한다.인덱스조정을 하는 번거러움을 줄여야하기 때문에 행 1줄과 열1줄을 미리 넣어주고 입력값을 넣어준다.
   

2. (N,M)까지 이동하기
   인접한 곳만 움직일 수 있기 때문에 상하좌우로만 이동이 가능하다.(dy,dx로 설정) y,x좌표가 1이상 n, m이하일때 이동이 가능하고 과거에 방문하지 않은 곳만 이동하도록 한다. (bfs사용)
   

3. 도착지까지 지나는 최소의 칸 수
   움직일 때마다 cnt를 세서 목표에 도착하면 cnt를 반환하도록 하였다. bfs는 최소 거리를 찾을 때 사용하기 때문에 제일 처음 도착지에 도착할 떄가 최소거리이다.
   

🥂코드

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

def move(x,y):
    dy = (1,0,-1,0)
    dx = (0,1,0,-1)
    visited = [[False for _ in range(m+1)] for _ in range(n+1)]
    queue = deque()
    queue.append((y,x,1))
    visited[y][x] = True

    while queue:
        ny,nx,nxt_cnt = queue.popleft()
        if ny==n and nx==m: return nxt_cnt
        for i in range(4):
            ey = ny + dy[i]
            ex = nx + dx[i]
            if 1 <= ey <= n and 1 <= ex <= m:
                if board[ey][ex]==1 and not visited[ey][ex]:
                    visited[ey][ex]=True
                    queue.append((ey,ex,nxt_cnt+1))

n,m = map(int,input().split())
board=[]

board.append([0]*(m+1))
for _ in range(n):
    li=[0]
    tmp = input().rstrip()
    for i in tmp:
        li.append(int(i))
    board.append(li.copy())

print(move(1,1))