[백준][Python][1261][BFS] 알고스팟

문제 : https://www.acmicpc.net/problem/1261

1261번: 알고스팟

BFS 문제다.

 

전형적인 탐색 문제고, 벽의 갯수를 Queue에 넣지 않고, 따로 lt 라는 리스트에 저장하여 풀었다.

하도 예전에 한거라 블로그 닉값한 문제인지 내가 푼건지 모르겠다.

 

import sys
from collections import deque
m,n = [int(i) for i in sys.stdin.readline().rstrip().split()]
arr = []
dx = [-1,1,0,0]
dy = [0,0,1,-1]

for i in range(n):
    arr.append([c for c in list(sys.stdin.readline().rstrip())])


lt = [[0]*m for _ in range(n)]
visited = [[False]*m for _ in range(n)]
q = deque()
q.append([0,0])
visited[0][0] = True
while q:

    cy,cx = q.popleft()
    if cy == n-1 and cx == m-1:
        print(lt[cy][cx])

        sys.exit()

    for i in range(4):
        ny,nx = cy+dy[i] , cx+dx[i]
        if 0<=ny<n and 0<=nx<m:
            if arr[ny][nx] == "1" and not visited[ny][nx]:
                lt[ny][nx] = lt[cy][cx] +1
                visited[ny][nx]=True
                q.append([ny,nx])
            elif arr[ny][nx] == "0" and not visited[ny][nx]:
                lt[ny][nx] = lt[cy][cx]
                visited[ny][nx] =True
                q.appendleft([ny,nx])