백준 2178: 미로 탐색 (Python)

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

2178번: 미로 탐색

 

이코테 교재에 있던 문제이기도 하고 어느 정도 그래프 탐색 문제에 익숙해져서 빠르게 풀었다

역시 사람은 복습이 중요하고 꾸준히 공부해야 한다,,,

이 문제 처음 풀었을 땐 답이 도무지 안 나왔는데 다시 푸니까 쉽게 풀림

 

from collections import deque

n, m = map(int, input().split())
miro = [[] for _ in range(n)]

for i in range(n):
    data = input()
    for j in range(m):
        miro[i].append(int(data[j]))


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

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

    while queue:
        qx, qy = queue.popleft()

        for i in range(4):
            mx = qx + dx[i]
            my = qy + dy[i]

            if mx < 0 or mx >= n or my < 0 or my >= m:
                continue

            if miro[mx][my] == 1:
                miro[mx][my] = miro[qx][qy] + 1
                queue.append([mx, my])

    return miro[n-1][m-1]

print(bfs(0,0))

 

나랑 가까운 곳부터 탐색해야 하니까 bfs로 풀었다

역시나 이동배열 만들어서 상하좌우 탐색해주고 길이 있는 곳으로 가면 원래 좌표의 값 + 1

어차피 미로는 한 길로 다 이어져있기 때문에 맨 처음 좌표로 bfs 돌리고 맨 마지막 좌표에 저장된 값을 출력해주면 된다!