문제

Baekjoon4485: 녹색 옷 입은 애가 젤다지?

  • 설명: (0, 0)부터 (n - 1, n - 1)까지 최단 경로로 이동하라.

풀이

  • 도둑루피를 획득하면 소지한 루피가 감소한다. 즉, 가중치를 $-$라고 생각하게 된다.
  • (0, 0)부터 (n - 1, n - 1)까지 링크가 잃어버리는 최소 금액이고 모든 가중치가 $-$이기 때문에 가장 큰 경로로 생각하기 쉽다.
  • 하지만 가중치를 $-$라고 생각하지말고 양수로 생각하면 반대로 동굴의 출구까지의 최단 경로를 구하면된다.
  • 양의 가중치가 있는 그래프에서 최단 경로는 Dijkstra로 구할 수 있기 때문에 그대로 적용해준다.

오늘의 회고

  • 처음에는 DP인가 했다. 하지만 초록색 옷을 입은 젤다 아니 링크가 상하좌우로 움직이기 때문에 DP로 풀 수가 없었다.
  • 하지만 가중치를 양수로 생각하면 그냥 최단경로를 구하는 것이기 때문에 단순히 구현만하면 되었다.
  • Python에서 우선순위 큐를 오랜만에(거의 4년..?) 쓰다보니 헷갈렸다.
  • 또 구현상 마냥 쉬운 알고리즘은 아니니 중간 중간 막혔다.
  • 답은 많이 푸는 것!

Code

# Baekjoon04485.py
import sys
input = sys.stdin.readline

from queue import PriorityQueue

MOVES = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def solve(t, n):
    cave = [list(map(int, input().split())) for _ in range(n)]

    pq = PriorityQueue()
    visited = [[False] * n for _ in range(n)]

    pq.put((cave[0][0], (0, 0)))

    ans = 0
    while pq.not_empty:
        cost, (curr_row, curr_col) = pq.get()
        if curr_row == n - 1 and curr_col == n - 1:
            ans = cost
            break

        if not visited[curr_row][curr_col]:
            visited[curr_row][curr_col] = True

            for row, col in MOVES:
                next_row, next_col = curr_row + row, curr_col + col
                if (0 <= next_row < n) and (0 <= next_col < n):
                    if not visited[next_row][next_col]:
                        pq.put((cave[next_row][next_col] + cost, (next_row, next_col)))

    print(f"Problem {t}: {ans}")

t = 1
n = int(input())
while n != 0:
    solve(t, n)
    t += 1
    n = int(input())

PS

  • 상하좌우면 무조건 DP가 아니었던 것은 아니었는데(그니까 상하좌우로 탐색하는데도 DP인 경우) 어떤 문제였는지 기억이 안난다 ㅎ 나중에 생각나면 풀고 포스팅하겠다.

+ Recent posts