[Baekjoon Online Judge] 백준 4485번 녹색 옷 입은 애가 젤다지?(Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 4485번 녹색 옷 입은 애가 젤다지?

(Python)

(글쓴날 : 2020.06.11)

 

---

* Baekjoon Online Judge, 백준 4485번 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

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

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/4485

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

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

칸을 지날 때마다 루피가 감소하는 N X N 크기의 동굴이 주어지고, (0, 0)에서부터 (N-1, N-1)까지 이동할 때, 잃을 수밖에 없는 최소 금액을 구하는 문제입니다.

 

저의 경우, 다익스트라를 적용하였고, Python을 사용했습니다.

우선, 동굴의 각 원소들을 정점으로 가정해 상하좌우로 이어진 원소끼리 간선으로, 해당 원소의 값을 가중치로 하는 인접 리스트를 구현한 뒤, 다익스트라를 적용하여 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

import sys, heapq
input = sys.stdin.readline
 
def BFS(hq):
    while hq:
        wei, vec = heapq.heappop(hq)
 
        if lupy[vec] > wei:
            lupy[vec] = wei
 
            for w, v in adjList[vec]:
                heapq.heappush(hq, (w+wei, v))
 
case = 0
while 1:
    N = int(input())
 
    if not N:
        sys.exit(0)
    case += 1
 
    cave = [list(map(int,input().split())) for _ in range(N)]
 
    INF = 2147483647
    lupy = [INF] * (N * N)
    lupy[0] = 0
    adjList= [[] for _ in range(N*N)]
 
    index = 0
    for i in range(N):
        for j in range(N):
            if i-1 >= 0:
                adjList[index].append((cave[i][j], (index-N)))
            if i+1 < N:
                adjList[index].append((cave[i][j], (index+N)))
            if j-1 >= 0:
                adjList[index].append((cave[i][j], (index-1)))
            if j+1 < N:
                adjList[index].append((cave[i][j], (index+1)))
 
            index += 1
 
    hq = []
    for w, v in adjList[0]:
        heapq.heappush(hq,(w,v))
 
    BFS(hq)
 
    print("Problem %d: %d" %(case, lupy[-1]+cave[-1][-1]))

---