240223 [BOJ/백준] 2178. 미로탐색

 

2178번: 미로 탐색 (acmicpc.net)

2178번: 미로 탐색

---

나의 코드

# 미로탐색
from collections import deque

N, M = map(int, input().split())
arr = [list(map(int, input())) for _ in range(N)]
visited = [[0]*M for _ in range(N)] # arr와 같은 빈 행렬 만들기
# print(arr)
di = [0, 1, 0, -1] #우, 하, 좌, 상 방향설정
dj = [1, 0, -1, 0]

def maze(si, sj):
    q = deque()
    q.append((si, sj))
    visited[si][sj] = 1

    while q:
        x, y = q.popleft()

        for k in range(4):
            new_i = x + di[k]
            new_j = y + dj[k]

            if 0 <= new_i < N and 0 <= new_j < M:
                if arr[new_i][new_j] == 1 and visited[new_i][new_j] == 0:
                    visited[new_i][new_j] = visited[x][y] + 1
                    q.append((new_i, new_j))

                if new_i == N-1 and new_j == M-1:
                    return visited[new_i][new_j]

print(maze(0,0))

 

결과

---

bfs에 대해 잘 알 수 있는 문제였다. 미루고 미루다 푼 미로탐색인데 전보다는 확실히 bfs의 진행과정을 알 수 있었고 그 과정을 생각하며 코드로 짤 수 있었다. 비슷한 문제를 풀면 bfs도 정복할 수 있을 것 같다!