[#2178] 미로 탐색

RookieAND·2022년 6월 16일

BFS 백준 코테

BaekJoon

목록 보기

17/42

❓ Question

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

📖 Before Start

BFS 탐색과 관련된 문제도 복습 차원에서 풀어보았다.

이번 문제는 너비 우선 탐색 (BFS) 을 통해 최적의 경로를 구해야 하는 문제였다.
알고리즘 설계도 막힘이 없었고, 코드 작성도 한번에 진행하여 문제를 해결하였다.

✒️ Design Algorithm

이차원 공간의 BFS 탐색은 거의 상하좌우 방향으로 뻗어나간다.

N X M 크기의 이차원 배열 안에 0 과 1 이 빠짐없이 전부 들어있다.
0 은 미로의 벽을 의미하며, 이곳으로는 탐색을 더 이상 진행할 수 없다.
1 은 미로의 길을 의미하며, 이곳으로는 추가적인 탐색을 진행할 수 있다.

기존의 지점에 오려면 지나야 하는 칸의 개수를 탐색 때마다 1씩 추가한다.

새로운 경로를 찾았다면, 기존의 위치까지 오려면 지나야 하는 칸의 개수에 1을 더한다.
그 후 이차원 배열에 더한 값을 추가하고, 탐색한 좌표를 tuple 형태로 덱에 추가한다.

💻 Making Own Code

✅ Correct Code

import sys
from collections import deque

read = sys.stdin.readline
N, M = map(int, read().split())
# 문자열로 읽어들인 목록을 map 함수로 분해해야 함.
maze = [list(map(int, read().strip())) for _ in range(N)]
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

# bfs 탐색을 통해 경로 탐색 시작.
def bfs(y, x):
    queue = deque([(y, x)])
    while queue:
        ny, nx = queue.popleft()
        for direct in direction:
            my, mx = ny + direct[0], nx + direct[1]
            # 유효한 탐색 범위 이내이면서, 아직 이동하지 않은 길목인지 탐색.
            if (0 <= my < N and 0 <= mx < M) and maze[my][mx] == 1:
                maze[my][mx] = maze[ny][nx] + 1
                queue.append((my, mx))

bfs(0, 0)
print(maze[N-1][M-1])