[백준 2178] 미로 탐색 Python

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

 

 

문제 풀이 전략

 

• BFS(Breadth-First Search) 활용: 최단 경로 문제에서는 현재 위치에서 가까운 곳부터 탐색하는 BFS가 적합합니다. DFS는 경로가 존재함을 확인하기엔 좋으나, 최단 거리를 보장하기 위해 별도의 처리가 필요하기 때문입니다.
• 방문 처리와 거리 계산의 통합: 별도의 방문 리스트(visited)를 만들 수도 있지만, 입력받은 미로 리스트 자체에 지금까지 이동한 거리(Step)를 직접 갱신하면 메모리를 아끼고 방문 여부도 동시에 체크할 수 있습니다.

 

해결 과정

1. 데이터 입력: 미로를 2차원 리스트로 입력받습니다. (이때 숫자가 붙어서 들어오므로 list(input())을 활용해 하나씩 쪼개줍니다.)
2. Queue 초기화: 시작점 (0, 0)을 deque에 넣고 방문 표시를 합니다.
3. 4방향 탐색: 큐에서 좌표를 하나씩 꺼내 상, 하, 좌, 우 네 방향을 확인합니다.
   • 미로 범위를 벗어나지 않는지 체크합니다.
   • 해당 칸이 이동할 수 있는 칸('1')인 경우에만 이동합니다.
4. 거리 갱신: 다음 칸의 값을 현재 칸의 값 + 1로 업데이트하여, 시작점으로부터의 거리를 기록합니다.
5. 결과 출력: 마지막 칸 (N-1, M-1)에 저장된 값을 출력합니다.

 

최종 코드

from collections import deque

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

def bfs(x, y):
    maze[y][x] = 1
    queue = deque([(x, y)])
    
    while queue:
        cx, cy = queue.popleft()

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            
            if 0 <= nx < width and 0 <= ny < height:
                if maze[ny][nx] == '1':
                    maze[ny][nx] = int(maze[cy][cx]) + 1
                    queue.append((nx,ny))



height,width = map(int, input().split())
maze = []
for i in range(height):
    maze.append(list(input()))

bfs(0,0)

print(maze[height-1][width-1])

 

 

 

 

어려웠던 점 및 주의사항

• 문자열과 숫자의 혼용: 처음에 미로를 문자열('1')로 입력받으면, 거리를 더할 때 int로 형변환을 해주어야 합니다. 위 코드에서는 처음부터 map(int, ...)를 사용하여 숫자로 변환해 관리함으로써 실수를 방지했습니다.
• 인덱스 주의: 문제에서는 (1, 1)부터 시작한다고 되어 있지만, 프로그래밍 배열 인덱스는 **(0, 0)**부터 시작하므로 이에 맞춰 좌표를 계산해야 합니다.