백준 1261 알고스팟

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1261

풀이

난이도 : Gold IV

1. 이 문제는 단순 최단거리 계산처럼 bfs를 이용하여 visited를 계산하는 방식으로 풀면 안된다.
   -> 당장 앞에 있는 벽을 부수고 가는 것처럼 bfs를 계산해버리면 멀리 돌아가는 더 빠른 방법을 계산할 수 없기 때문이다.
2. dp를 이용하여 bfs처럼 기록해 나간다.
3. 단, 그냥 bfs가 아니라 dijkstra 알고리즘을 이용하여 최단 경로를 갱신해 나간다.
4. graph에서처럼 우선순위 큐를 사용하지 않고 일반 queue를 사용하며, bfs로 탐색을 해나가면서 기존 dp에 있던 값과 '현재 값 + 벽의 유무(0 or 1)' 중 작은 값으로 기록을 하는 방법을 사용한다.
5. queue에는 모든 방향을 무조건 넣는 것이 아니라 작은 값을 업데이트 해주었을 경우에만 queue에 좌표를 추가해준다.

👉 처음에는 단순 bfs로 풀었다가 시간초과와 틀렸다는 결과를 받았는데, dp를 어떻게 최신화시키면서 탐색하여 목적지까지 갈 수 있을지 생각하다가 풀이를 생각하게 되었다.
👉 다익스트라 알고리즘이 배열에서 적용되는 개념을 잡을 수 있었다.

코드

    from collections import deque

    n, m = map(int, input().split())

    graph = []
    dp = [[int(1e9)] * n for _ in range(m)]

    for _ in range(m):
        tmp = []
        numbers = str(input())
        for number in numbers:
            tmp.append(int(number))
        graph.append(tmp)

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

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

        while q:
            x, y = q.popleft()

            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]

                if nx < 0 or ny < 0 or nx >= m or ny >= n:
                    continue
                if dp[x][y] + graph[nx][ny] < dp[nx][ny]:
                    dp[nx][ny] = dp[x][y] + graph[nx][ny]
                    q.append([nx, ny])


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