boj2178-미로탐색

dust_potato·2021년 5월 8일
0

코딩테스트

목록 보기
3/23

문제 : 미로탐색

import sys
from collections import deque

if __name__ == "__main__":
    input = sys.stdin.readline
    row, col = map(int, input().split())

    graph = []
    for i in range(row):
        graph.append(list(map(int, input().rstrip())))
    # print(graph)

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

    q = deque()
    q.append([0,0])

    while q:
        x , y = q.popleft()
        for i in range(4):
            tx = x + dx[i]
            ty = y + dy[i]
            if 0 <= tx < row and 0 <= ty < col and graph[tx][ty] == 1:
                q.append([tx, ty])
                graph[tx][ty] = graph[x][y] + 1

    # print('result: ' , graph)
    print(graph[row-1][col-1])

0,0 부터 시작해서 상하좌우를 탐색하는 bfs
q에 넣을 때마다 해당 좌표의 값 +1

관심 있을 만한 포스트

0개의 댓글