(BOJ) 제2178호: 미로 탐색

문제

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

설명

검색 문제로 dfs나 bfs 알고리즘으로 해결이 가능할 수도 있다고 생각했는데 dfs를 쓰면 안 된다.

최소 통과하려면 현재 위치에서 가장 가까운 도로를 찾아야 합니다.

즉, 너비 우선 탐색을 사용하여 문제를 해결해야 합니다.

bfs는 대기열을 사용하여 구현할 수 있습니다.

전체 코드

import sys
input = sys.stdin.readline

n,m = map(int, input().split())
arr=()
visited=()
queue=()
cnt=()
for i in range(n):
    number = input().rstrip()
    row = list(map(int,str(number)))
    arr.append(row)
    visited.append((0)*m)
    cnt.append((0)*m)

dx = (0,0,1,-1)
dy = (1,-1,0,0)

queue.append((0,0))
visited(0)(0)=1
cnt(0)(0)+=1


while(len(queue)>0):
    for k in range(4):
        x = queue(0)(1)+dx(k)
        y = queue(0)(0)+dy(k)
        if x<m and x>=0 and y<n and y>=0:
            if visited(y)(x)==0 and arr(y)(x)==1:
                queue.append((y,x))
                cnt(y)(x)=cnt(queue(0)(0))(queue(0)(1))+1
                visited(y)(x)=1
            if (x==m-1 and y==n-1):
                #print(cnt(n-1)(m-1))
                break
    queue.pop(0)
    


print(cnt(n-1)(m-1))