SWEA #5250 (그래프의 최소비용-7일차) 최소비용 Python(파이썬), 다익스트라를 이용해서 구현해보기

1. 문제는 이쪽으로

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

2. bfs

처음에는 수업시간에 배운 다익스트라를 이용해서 풀이해 보려고 했지만,

시간복잡도 때문인지 자꾸 시간초과가 나서 bfs를 변형한 방법으로 풀이하였다.

from collections import deque
di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]
def bfs(i, j): # s는 시작지점
    q = deque()
    q.append((i,j))
    money[i][j] = 0 # 시작지점의 가격 처리

    while q:
        l = len(q)
        for _ in range(l):
            si, sj = q.popleft()
            for d in range(4):
                ni, nj = si+di[d], sj+dj[d]
                if 0 <= ni < N and 0 <= nj < N :

                    mon = money[si][sj] + 1
                    if hs[ni][nj] > hs[si][sj]:
                        mon += hs[ni][nj] - hs[si][sj]

                    if mon < money[ni][nj]:
                        q.append((ni, nj))
                        money[ni][nj] = mon


T = int(input())
for tc in range(1, T+1):
    N = int(input())
    hs = [list(map(int, input().split())) for _ in range(N)]
    money = [[10000]*N for _ in range(N)]
    bfs(0, 0)
    print(f"#{tc} {money[N-1][N-1]}")

3. 다익스트라

주말에 다익스트라를 복습하고 나서 최소힙을 응용해서 다익스트라로 구현해보았다.

import heapq

di = [-1, 1, 0, 0]
dj = [0, 0, -1, 1]
T = int(input())
for tc in range(1, T+1):
    N = int(input())
    heights = [list(map(int, input().split())) for _ in range(N)]
    fuels = [[100000]*(N) for _ in range(N)]

    q = []
    fuels[0][0] = 0
    heapq.heappush(q, (0, 0, 0))
    find = False
    while q:
        dist, si, sj = heapq.heappop(q)
        for d in range(4):
            ni, nj = si + di[d], sj + dj[d]

            if 0 <= ni < N and 0 <= nj < N:
                if fuels[ni][nj] < dist:
                    continue
                cost = dist + 1
                if heights[ni][nj] > heights[si][sj]:
                    cost = cost + heights[ni][nj] - heights[si][sj]

                if cost < fuels[ni][nj]:
                    fuels[ni][nj] = cost
                    heapq.heappush(q, (cost, ni, nj))



    print(f"#{tc} {fuels[N-1][N-1]}")

처음에는 마찬가지로 시간초과가 발생하였으나,

if cost < fuels[ni][nj]:
                    fuels[ni][nj] = cost
                    heapq.heappush(q, (cost, ni, nj))

이 부분, 즉 최소값이 발생하였을 때만 힙에 추가해주는 방식으로 가짓수를 줄여주었더니 Pass 하였다.

Uploaded by N2T