1261번 알고스팟 백준 파이썬

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

1261번: 알고스팟

이 문제를 풀기 전에 숨바꼭질3을 먼저 풀어볼 것을 권장한다. 이 두문제는 비슷한 면이 많이 있다.(www.acmicpc.net/problem/13549)

 

여기에서 중요한 포인트는 어떤 것을 먼저 할 것이냐를 결정하는 것이다.

import sys
from collections import deque
N,M=map(int,sys.stdin.readline().rstrip().split())
graph = [list(map(int,sys.stdin.readline().rstrip())) for _ in range(M)]
visited =[[False]*N for _ in range(M)]
dy=[1,-1,0,0]
dx=[0,0,1,-1]
def scope(y,x):
    if y>=0 and y<M and x>=0 and x<N:
        return True
    else:
        return False
def bfs():
    q=deque()
    q.append([0,0])
    visited[0][0]=True
    while q:
        fy,fx=q.popleft()
        if fy==M-1 and fx ==N-1:
            print(graph[fy][fx])
            break
        for i in range(4):
            my=fy+dy[i]
            mx=fx+dx[i]
            if scope(my,mx):
                if not visited[my][mx] and graph[my][mx]==0:
                    visited[my][mx]=True
                    graph[my][mx]=graph[fy][fx]
                    q.appendleft([my,mx])
                elif not visited[my][mx] and graph[my][mx]!=0:
                    visited[my][mx]=True
                    graph[my][mx]=graph[fy][fx]+1
                    q.append([my,mx])
bfs()
 

위의 설명을 코드로 표현하면 다음과 같이 된다.