[Python/Baekjoon] 2178. 미로 탐색

💬 문제

문제 난이도: 백준 실버 1

문제 링크: https://www.acmicpc.net/problem/2178

❗️접근 방법

시작 위치와 도착 위치가 주어지고
도착 위치까지 갈 수 있는 최소 비용을 묻는 문제이므로,
BFS를 사용하면 된다.

✅ 정답 코드

# 미로 탐색 # BFS
import sys
from collections import deque
input = sys.stdin.readline
print = sys.stdout.write

N, M = map(int, input().split(' '))
miro = []
for _ in range(N):
    miro.append(list(map(int, list(input().rstrip()))))

def bfs():
    queue = deque([[0, 0]])  
    # 현재 위치에서 움직일 수 있는 4가지 방향
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x+dx[i] 
            ny = y+dy[i]
            # visited가 필요하지 않는 이유는 miro의 초기값이 + 연산으로 바뀌기 때문에
            # 1 or 0: not visited, else: visited
            if 0<=nx<N and 0<=ny<M and miro[nx][ny] == 1:
                miro[nx][ny] = miro[x][y] + 1 # 가는 순서대로 넣어주면 n,m에는 n,m까지 가는 최단 거리가 들어있게 됨
                queue.append([nx, ny])
    return miro[N-1][M-1]
            
print(f'{bfs()}')

✍️ 새롭게 알게 된 부분

• 시작 위치에서 시작해서 어떠한 방법으로라도 처음으로 도착 지점에 방문한 그 순간이 최소 비용으로 간 경우이다.
• visited가 따로 필요하지 않다.
• 0으로 초기화 되어 있는 miro라는 이차원 배열에 비용을 더해주면서 탐색하기 때문이다.
• 즉, 0이면 아직 방문하지 않았다는 의미이기도 하다.
  (유사한 방법을 사용한 풀이: https://velog.io/@jnl1128/PythonBaekjoon-1707.-%EC%9D%B4%EB%B6%84-%EA%B7%B8%EB%9E%98%ED%94%84)