[BOJ] 2178. 미로 탐색 (Python/BFS/Silver 1)

[Baekjoon] 2178. 미로 탐색

Silver 1 | #BFS #최단경로

문제 바로가기 🔗

1. 문제 요약 및 풀이 방식

(1, 1)에서 출발하여 (N, M) 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다.

• 최단 거리 = BFS: 모든 간선의 가중치가 동일할 때 최단 경로를 보장하는 BFS를 사용한다.
• 거리 업데이트: 다음 칸으로 이동할 때 현재 칸의 값 + 1을 저장하여 방문 여부와 거리를 동시에 관리한다.

2. 전체 코드 (Python)

import sys
from collections import deque
input = sys.stdin.readline

# 데이터 입력 시 미리 int형 리스트로 변환 (최적화)
N, M = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(N)]

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

def bfs():
    queue = deque([(0, 0)])
    
    while queue:
        x, y = queue.popleft()
        
        # 도착지 도달 시 결과 반환
        if x == N - 1 and y == M - 1:
            return graph[x][y]
        
        for k in range(4):
            nx, ny = x + dx[k], j + dy[k] # 상하좌우 탐색
            
            if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))
    return -1

print(bfs())

3. 🚀 과거 풀이와 비교: 무엇이 달라졌나?

예전에 작성했던 풀이(포스팅 #132)를 다시 훑어보니, 그때와 지금의 접근 방식에 꽤 큰 차이가 느껴졌다.

• 구현의 숙련도: 예전에는 로직을 짜면서 꽤 버벅거렸던 기억이 나는데, 지금은 BFS의 흐름을 명확히 이해하고 있어 막힘없이 수월하게 풀 수 있었다.
• 효율성(Performance) 고려: 예전 코드는 단순히 '정답을 맞히는 것'에 급급해 데이터 타입 변환이나 연산 비용을 전혀 신경 쓰지 않은 게 보였다. 이번에는 입력 단계에서 미리 int 변환을 처리하는 등 미세한 성능까지 고려하며 코드를 짰다.
• 상세 설명 참고: 원리에 대한 아주 기초적인 설명은 예전 포스팅(#132)에 더 자세히 적혀 있지만, 전체적인 코드의 퀄리티는 확실히 지금이 더 나아진 것 같다.

4. ✍️ 회고: 견고한 코드 작성하기

✔ 데이터 타입 최적화의 중요성

탐색 루프 내부에서 매번 int() 형변환을 하는 것은 불필요한 부하를 준다. 리팩토링 과정에서 이를 초기에 처리하도록 바꾼 것만으로도 훨씬 깔끔한 코드가 되었다.

---

💡 배운 점

• BFS는 큐에서 먼저 나오는 경로가 반드시 최단임을 보장한다.
• 미로가 막혀 도착하지 못하는 극단적인 경우를 대비해 return -1 처리를 습관화하자.