[파이썬, Python] 백준 2178: 미로 탐색

문제

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

2178번: 미로 탐색

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
s= []
que = []
dx = [1, -1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(n):
    s.append(list(input()))
que = [[0, 0]]
s[0][0] = 1

while que:
    a, b = que[0][0], que[0][1]
    del que[0]
    for i in range(4):
        x = a + dx[i]
        y = b + dy[i]
        if 0<= x < n and 0 <= y < m and s[x][y] == "1":
            que.append([x, y])
            s[x][y] = s[a][b] + 1
print(s[n-1][m-1])

설명

우선 미로를 저장할 s라는 리스트를 만들고, que를 저장할 리스트도 하나 만든다.
그리고 dx, dy라는 리스트를 만드는데 dx는 x축으로 이동하는 좌표, dy는 y축으로 이동하는 좌표이다.
[dx][dy]의 형태로 사용할 예정이고 [1][0], [-1][0], [0][-1], [0][1] 이런 식으로 활용이 된다.

que에 시작점의 역할을 할 [0, 0]을 넣어준다.
s[i][j]의 경우 미로의 i행 j열의 값으로, 0은 이동이 불가능, 1은 이동이 가능하다는 것을 나타낸다.
s[0][0]의 경우 출발점을 나타낸다.

que가 존재하는 동안, a와 b는 que의 x값과 y값을 가진다.
이후 que에 존재하던 값을 삭제해 주고, 갈 수 있는 방향을 탐색한다.
만약에 0부터 n 사이 0부터 m 사이에 갈 수 있는 공간이 존재한다면(미로를 벗어나지 않는 좌표),
que의 값에 그 좌표를 추가하고 s[x][y]의 값을 s[a][b]에 1 더한 값으로 지정해 준다.(칸을 이동하면 1 증가하기 때문)

이후 입력 받은 좌표의 값을 출력한다.