BFS
너비 우선 탐색. 가까운 노드부터 탐색하는 알고리즘
동작원리 - 큐 / 구현 방법 - 큐 자료구조 이용

✅ 문제

현재 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한 번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

입력 예시

5 6
101010
111111
000001
111111
111111

출력 예시

10

➕ 문제 해설

BFS를 이용하여 해결
시작 지점에서 가까운 노드부터 차례대로 노드를 탐색하여, 모든 노드의 시작 지점부터 현재 노드까지의 거리 정보를 넣어주면 된다.
처음 방문한 노드는 queue에 모두 넣어 준다.

from collections import deque

N, M = map(int, input().split())
miro_map = []

for i in range(N):
    miro_map.append(list(map(int,input())))

step = [(-1,0), (1, 0), (0, -1), (0, 1)]

def bfs(x, y):
    queue = deque()
    queue.append((x,y))
    while queue:
        x, y = queue.popleft()
        # 상, 하, 좌, 우 모두 방문
        for i in range(4):
            nx = x + step[i][0]
            ny = y + step[i][1]
            if nx < 0 or nx >= N or ny < 0 or ny >= M:
                continue
            if miro_map[nx][ny] == 0:
                continue
            # 다음 노드가 처음 방문 한 경우, 현재 노드보다 거리가 한 칸 더 멀다
            if miro_map[nx][ny] == 1:
                miro_map[nx][ny] = miro_map[x][y] + 1
                queue.append((nx, ny))

    return miro_map[N-1][M-1]

print(bfs(0,0))

📝 정리

아직 bfs, dfs를 문제에 적용하는 데 익숙하지 않아 아이디어를 떠올리는 것이 어렵다..