백준 1261 [알고스팟] 파이썬

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

 

# 백준 1261 알고스팟
# 목표: (0,0) → (N-1, M-1)까지 이동할 때, 부숴야 하는 벽의 최소 개수를 구하는 문제
#       이동 시 빈 칸(0)은 비용 0, 벽(1)은 비용 1로 취급하여 다익스트라(우선순위 큐)로 해결

dr = [0, 0, -1, 1]  # 행 이동 (상하좌우)
dc = [1, -1, 0, 0]  # 열 이동 (상하좌우)

import sys, heapq
input = sys.stdin.readline

M, N = map(int, input().split())  # M=열, N=행 (주의: 문제에서 순서 반대)
field = []
for _ in range(N):
    # 미로 정보 입력 (0=빈 방, 1=벽)
    field.append(list(map(int, input().rstrip())))

# 우선순위 큐 (heapq 사용 → 다익스트라)
# 원소 형태: (부순 벽 개수, 행, 열)
q = []

# 방문 여부 기록
visited = [[False for _ in range(M)] for _ in range(N)]

# 각 좌표까지 도달하는 최소 벽 부순 횟수 저장 배열
cnt = [[0 for _ in range(M)] for _ in range(N)]

# 시작점 (0,0)에서 출발, 부순 벽 개수 = 0
heapq.heappush(q, (0, 0, 0))
visited[0][0] = True

while q:
    wall_cnt, row, col = heapq.heappop(q)  # 현재 위치와 지금까지 부순 벽 개수
    
    for i in range(4):  # 상하좌우 탐색
        R = row + dr[i]
        C = col + dc[i]
        
        # 미로 범위 안에 있고, 아직 방문하지 않았다면
        if 0 <= R < N and 0 <= C < M and not visited[R][C]:
            visited[R][C] = True  # 방문 처리
            
            if field[R][C]:  # 벽(1)이라면
                # 벽을 하나 더 부숴야 하므로 비용 +1
                heapq.heappush(q, (wall_cnt + 1, R, C))
                cnt[R][C] = wall_cnt + 1
            else:  # 빈 방(0)이라면
                # 추가 비용 없이 그대로 진행
                heapq.heappush(q, (wall_cnt, R, C))
                cnt[R][C] = wall_cnt

# (N-1, M-1)에 도착했을 때 부순 벽의 최소 개수 출력
print(cnt[N-1][M-1])

# print(cnt)  # 전체 cnt 배열을 보고 싶으면 사용

BFS인데 HEAPQ를 이용한 문제이다. (굳이 따지자면 다익스트라 알고리즘도 사용했다고 볼 수 있다.)