백준 1261 알고스팟

과정

• BFS, 다익스트라
• 부수는 벽의 개수를 최소화해서 도착하는 경우를 출력한다.
• 0-1 BFS도 사용가능하다 (가중치가 0, 1뿐이므로)

다익스트라 풀이

import heapq

# N = int(input())
N, M = map(int, input().split())
INF = 1e9

dp = [[INF for _ in range(N)] for _ in range(M)]

map_lst = [list(map(int, input())) for _ in range(M)]

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

def dijkstra(x, y):
    q = []
    heapq.heappush(q, (map_lst[y][x], x, y))
    dp[y][x] = map_lst[y][x]

    while q:
        wall, x, y = heapq.heappop(q)
        # 이미 처리된 곳이면
        if dp[y][x] < wall:
            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 = wall + map_lst[ny][nx]
            # 기존 값보다 작으면
            if dp[ny][nx] > cost:
                dp[ny][nx] = cost
                heapq.heappush(q, (cost, nx, ny))

dijkstra(0, 0)
print(dp[-1][-1])

BFS 풀이

from collections import deque

N, M = map(int, input().split())
INF = 1e9

dp = [[INF for _ in range(N)] for _ in range(M)]

map_lst = [list(map(int, input())) for _ in range(M)]

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

def bfs(x, y):
    q = deque([(x, y, 0)])
    dp[y][x] = map_lst[y][x]

    while q:
        x, y, wall = q.popleft()
        # 이미 처리된 곳이면
        if dp[y][x] < wall:
            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 = wall + map_lst[ny][nx]
            # 기존 값보다 작으면
            if dp[ny][nx] > cost:
                dp[ny][nx] = cost
                q.append((nx, ny, cost))

bfs(0, 0)
print(dp[-1][-1])

생각

• BFS와 다익스트라의 차이에 대해 생각했다.
• 기존에 BFS문제에서 deque를 사용할 때, 일반적으로 좌표 또는 인덱스 값을 넣지만, 특정 조건이 주어지는 경우에는 (ex. 이동 횟수) 좌표와 함께 조건에 관한 내용을 같이 튜플에 넣기도 했다.
• 가중치와 좌표를 함께 넣는 BFS와 다익스트라는 어떤 차이가 있을 지 생각했다.
• deque를 사용했어도 가중치를 처리하는 과정이 있으면 다익스트라와 동일하다고 생각한다.
  • 특정 알고리즘에서는 특정 자료구조만을 사용해야 한다는 식으로 생각하지 말아야겠다.
• 다익스트라는 가중치에 음수가 섞인 경우 사용하지 못한다.
• 이 문제의 경우 BFS말고 0-1 BFS를 사용하면 좋다고 한다. (시간복잡도가 V+E)
• BFS: 124ms, 다익스트라: 72ms

참고