백준-1261-알고스팟

문제

알고스팟

풀이

문제조건 해석

(1, 1)부터 (N, M)까지 이동할 때 최소로 벽을 부수는 경우 찾기

1. 빈 방은 자유롭게 이동 가능
2. 벽은 부숴야만 이동 가능
3. 벽을 부수면 빈 방이 된다
4. 상하좌우로만 이동 가능

처음에는 BFS로 찾아보려 했으나 생각이 나지 않아 다익스트라를 적용했다. BFS에 우선순위 큐 적용해도 간단하게 풀이가 가능했다.꾸준함 블로그

알고리즘

다익스트라 알고리즘에서

1. 빈 방에 대해서는 가중치를 0으로 하는 노드로,
2. 벽이 있는 경우는 가중치가 1인 노드로,
3. 인접한 노드는 상하좌우 방으로 생각하면 된다.

dist[n][m] : (n, m) 노드까지의 최단경로, 인접 정점 순회시마다 업데이트한다.

$O(MN)$의 시간복잡도

코드

from sys import stdin
import heapq

input = stdin.readline
m, n =[int(_) for _ in input().rstrip().split()]
maze = []
for _ in range(n):
    maze.append([int(x) for x in input().rstrip()])
MAX_DIST = 200
dist = [[MAX_DIST for _ in range(m)] for __ in range(n)]
dist[0][0] = 0
pq = [(0, (0, 0))]

while pq:
    w, u = heapq.heappop(pq)
    ui, uj = u
    if ui == n-1 and uj == m-1:
        print(dist[n-1][m-1])
        break
    if w > dist[ui][uj]: # 큐에 넣었던 경로보다 더 짧은 경로로 업데이트되었을 때
        continue
    for di, dj in [(0, -1), (-1, 0), (0, 1), (1, 0)]:
        vi, vj = ui+di, uj+dj
        if not (0<=vi<n and 0<=vj<m):
            continue
        if maze[vi][vj]: # 벽이 있으면
            if dist[ui][uj]+1 < dist[vi][vj]:
                dist[vi][vj] = dist[ui][uj]+1
                heapq.heappush(pq, (dist[vi][vj], (vi, vj)))
        else: # 벽이 없으면
            if dist[ui][uj] < dist[vi][vj]:
                dist[vi][vj] = dist[ui][uj]
                heapq.heappush(pq, (dist[vi][vj], (vi, vj)))

예시 입력
6 6
001111
010000
001111
110001

결과 dist배열
[[0, 0, 1, 2, 2, 2], 
 [0, 1, 1, 1, 1, 1], 
 [0, 0, 1, 2, 2, 2], 
 [1, 1, 1, 1, 1, 2], 
 [1, 2, 2, 1, 2, 2], 
 [2, 1, 1, 1, 2, 2]]

배운점

• 다익스트라와 우선순위 큐를 적용한 BFS는 꽤 유사하다
• 문제를 잘 추상화해서 알고리즘 적용할 수 있어야 한다.
• 유사 문제
  • 최단경로