[BaekJoon 4485 : 다익스트라, Python] - 녹색 옷 입은 애가 젤다지?

2021, Nov 05    


백준 1446 녹색 옷 입은 애가 젤다지? : 골드 4



Solution


BFS + DIKJSTRA + 맵 구현


import sys
input = sys.stdin.readline
from heapq import *

def solve(n, cost_map):
    dirs = [(-1, 0), (0, -1), (0, 1), (1, 0)]         # 모든 좌표는 (r, c)
    min_cost = [[float('inf') for _ in range(n)] for _ in range(n)]     # (k, l) 까지 이동하는 데 걸린 최소 cost
    hq = []
    heappush(hq, [cost_map[0][0], (0, 0)] )      
    while hq:
        c_cost, (c_r, c_c) = heappop(hq)
        for d in dirs:
            n_r, n_c = c_r + d[0], c_c + d[1]
            if 0 <= n_r < n and 0 <= n_c < n and min_cost[n_r][n_c] > c_cost:
                n_cost = c_cost + cost_map[n_r][n_c]
                if min_cost[n_r][n_c] > n_cost:
                    min_cost[n_r][n_c] = n_cost
                    heappush(hq, [n_cost, (n_r, n_c)])

    return min_cost[-1][-1]

caves = []
while True:
    try:
        n = int(input())
        if n == 0: break
        caves.append([list(map(int, input().split())) for _ in range(n)])
        print("Problem {}: {}".format(len(caves), solve(n, caves[-1])))
    except:
        break


풀이과정 및 느낀점


이번 문제는 BFS + 다익스트라 + 그래프 구현 이 세 가지 알고리즘이 적절히 섞인 문제였다.
다익스트라 알고리즘에서 존재하는 노드 간의 연결성 및 간선 가중치 값 정보를 이 문제에서는 동굴에서 가능한 이동방향과 (dirs) 각 좌표에서의 루피(cost) 가 대체해준다.
때문에 heapq 를 통해 연결된 좌표들 중에서 최소 비용을 가진 좌표만을 계속 반환해주면서, 그 좌표를 방문해서 해당 좌표까지 이동하는 데 걸리는 현재까지의 최소 cost 를 min_cost 값으로 갱신해주면 된다.

그리고 이 문제의 또 다른 포인트는 input 을 받는 코드인데, 보통의 경우 입력은 하나의 케이스만이 주어지거나, 혹은 정확히 몇 개의 test case 를 수행할 건지 개수 자체가 명시가 되어 그 만큼만 for 문을 돌려 입력을 받으면 된다.
하지만 이 문제 같은 경우 테스트 케이스의 개수가 고정되어 있지 않아서 while True + try-except 로 일단 계속 input 을 받고, 더이상 input 이 입력되지 않아 오류가 뜨면 그 때 while 문을 탈출하도록 해줬다.

좀 급하게 풀긴 했지만 나름 신선한 문제였다.

# BaekJoon # Python # dikjstra # 다익스트라 # 그래프 # Algorithm