백준2178번 미로탐색(BFS)

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

최단거리이기 때문에 BFS를 사용한다.

다시정리:
DFS 스택사용, 이동과정을 할때 주로계산
BFS 큐 사용 , 최단거리 계산할때 주로계산

미로같은 탐색을 할때에는 상하좌우에 대한 좌표를 설정해야한다.
(이런 패턴을 외워둬야할듯..)

상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

입력받는값
N,M = map(int,input().split())

for i in range(N):
graph.append(list(map(int,input().strip())))

-> MAP = [[int(i) for i in list(input())] for _ in range(N)] 가능하다함.

만약 strip이 아닌 split()로 하면 아래와 같은 값이나옴
[[101111], [101010], [101011], [111011]]

strip경우
[[1, 0, 1, 1, 1, 1], [1, 0, 1, 0, 1, 0], [1, 0, 1, 0, 1, 1], [1, 1, 1, 0, 1, 1]]

from collections import deque

def bfs(x,y):
    queue = deque()
    queue.append((x,y))

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            nx = x+dx[i]
            ny = y+dy[i]

            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y]+1
                queue.append((nx,ny))
    return graph[-1][-1]
          #graph[N-1][M-1]

N,M = map(int,input().split())

graph = []

for i in range(N):
    graph.append(list(map(int,input().strip())))

dx = [-1,1,0,0]
dy = [0,0,-1,1]

print(bfs(0,0))