[Dijkstra] BOJ 1261 알고스팟

 

🎈 백준 1261 알고스팟

www.acmicpc.net/problem/1261

1261번: 알고스팟

 

❗ 문제의 핵심, 풀이 과정

• 미로는 N*M 크기이며, 총 1*1크기의 방으로 이루어져 있다. 미로는 빈 방 또는 벽으로 이루어져 있고, 빈 방은 자유롭게 다닐 수 있지만, 벽은 부수지 않으면 이동할 수 없다.

• 현재 운영진이 (x, y)에 있을 때, 이동할 수 있는 방은 (x+1, y), (x, y+1), (x-1, y), (x, y-1) 이다. 단, 미로의 밖으로 이동 할 수는 없다.

=> 각 방(미로의 위치)을 하나의 노드라고 생각한다. 이동할 수 있는 방은 현재 방에서의 인접한 상하좌우 방이다.

 

• 현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오.

=> (x1, y1)에서 (x2, y2)로 이동했을 때 (x2, y2)의 값을 이동 비용이라고 생각할 수 있다.

=> 즉, (1, 1) 노드에서 (n, n) 노드까지 이동하기 위해 벽을 최소로 부수는 개수는  (1, 1) 노드에서 (n, n) 노드까지의 최단 경로이다. (다익스트라 알고리즘)

 

✅ 전체 코드

import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)

# 상하좌우 이동
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

m, n = map(int, input().split())
graph = []
distance = [[INF] * m for _ in range(n)]
for _ in range(n):
    graph.append(list(map(int, input().rstrip())))

# 시작 위치 초기화
x, y = 0, 0
q = []
heapq.heappush(q, (0, x, y))
distance[x][y] = 0

while q:
    dist, x, y = heapq.heappop(q)
    # 이미 처리된 경우
    if distance[x][y] < dist:
        continue
    # 상하좌우 인접한 노드 확인
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        cost = dist + graph[nx][ny]
        if cost < distance[nx][ny]:
            distance[nx][ny] = cost
            heapq.heappush(q, (cost, nx, ny))

print(distance[n-1][m-1])