[백준 파이썬] 4485 녹색 옷 입은 애가 젤다지?

 

https://www.acmicpc.net/problem/4485

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

문제

 

N*N의 배열에서 [0][0] 에서 [N-1][N-1]까지의 경로중 가장 적은양의 Cost가 필요한 길을 찾는 문제이다. 

 

---

 

풀이

가장 작은 Cost를 구하는 BFS문제이므로 다익스트라 알고리즘을 사용하였다.

def dijsktra(startCost):
    q = []
    heapq.heappush(q, (startCost, 0, 0))
    distance[0][0] = startCost
    while q:
        cost, r, c = heapq.heappop(q)
        if cost > distance[r][c]:
            continue
        for i in range(4):
            nr = r + dx[i]
            nc = c + dy[i]
            if 0 <= nr < N and 0 <= nc < N:
                newCost = cost + graph[nr][nc]
                if newCost < distance[nr][nc]:
                    distance[nr][nc] = newCost
                    heapq.heappush(q, (newCost, nr, nc))

 

 

기존 다익스트라와 다르게 배열을 사용했기 때문에 우선순위 큐에 cost, row, column 3개의 정보를 넣어주었다.

이후 순회를 위한 조건 (코스트 값이 더 적음)을 만족하면 큐에 넣은 후 탐색을 계속하는 방식을 사용하였다.

 

 

 

코드

import sys
import heapq

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

def dijsktra(startCost):
    q = []
    heapq.heappush(q, (startCost, 0, 0))
    distance[0][0] = startCost
    while q:
        cost, r, c = heapq.heappop(q)
        if cost > distance[r][c]:
            continue
        for i in range(4):
            nr = r + dx[i]
            nc = c + dy[i]
            if 0 <= nr < N and 0 <= nc < N:
                newCost = cost + graph[nr][nc]
                if newCost < distance[nr][nc]:
                    distance[nr][nc] = newCost
                    heapq.heappush(q, (newCost, nr, nc))
                    


while True:
    N = int(input())
    if N == 0:
        break
    graph = [list(map(int, input().split())) for _ in range(N)]
    distance = list([sys.maxsize] * N for _ in range(N))
    dijsktra(graph[0][0])
    print("Problem ", end="")
    print(cnt, end="")
    print(": ",end="")
    print(distance[N-1][N-1])
    cnt += 1