[백준/Python] 2178 미로 탐색

 

 

 

• bfs, flood fill을 이용하여 시작점에서 끝점까지 이동할수 있는 칸을 지나며 +1을 해주고 끝 인덱스의 값을 출력하였다.

 

from collections import deque

N,M = map(int,input().split())
arr = [list(map(int,input())) for _ in range(N)]
used = [[0]*M for _ in range(N)] # used 배열을 통한 중복 접근 방지
directy = [-1,1,0,0]
directx = [0,0,-1,1]

def bfs(y,x):

    q = deque([(y,x)])
    while q:
        y,x = q.popleft()
        for k in range(4):
            dy = directy[k] + y
            dx = directx[k] + x

            if dy >= N or dy < 0 or dx >= M or dx < 0: # 배열 범위를 벗어나면 continue
                continue
            if arr[dy][dx] == 1 and used[dy][dx] == 0: # 갈 수 있는 길이면서, 한번도 가지 않았던 곳이라면
                used[dy][dx] = 1 # used에 체크해주고
                arr[dy][dx] = arr[y][x] + arr[dy][dx] # 목표방향에 현재위치의 값을 더함
                q.append([dy,dx])

used[0][0] = 1 # 출발점의 used를 1로 바꾸고 bfs시작
bfs(0,0)
print(arr[-1][-1])