미로 탐색

백준 2178번: 미로 탐색

아이디어

기본적인 bfs 문제다. 한 칸 이동할 때마다 값을 1씩 증가시켜서 총 몇 칸 이동했는지 센다.

코드

from collections import deque

N, M = map(int, input().split())
graph = [list(map(int, list(input()))) for _ in range(N)]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs():
    q = deque()
    q.append((0, 0))
    while q:
        row, col = q.popleft()
        for i in range(4):
            nextRow = row + dy[i]
            nextCol = col + dx[i]
            if nextRow < 0 or nextRow >= N or nextCol < 0 or nextCol >= M:
                continue
            elif graph[nextRow][nextCol] != 1:
                continue
            else:
                graph[nextRow][nextCol] = graph[row][col] + 1
                q.append((nextRow, nextCol))


bfs()
print(graph[N - 1][M - 1])

여담

어떻게 하면 입력받는 코드를 한 줄로 만들 수 있을까 고민하다

graph = [list(map(int, list(input()))) for _ in range(N)]

이런 길쭉한 코드가 나왔다.
input받은 문자열을 list로 만들고, map으로 하나하나 정수로 만들고 다시 list로 만들었다.

bfs dfs 눈감고도 만들 수 있을 정도로 연습해야겠다.