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

문제의 포인트

격자 탐색에서 최소비용을 구하는 문제
다익스트라를 활용해서 최소비용을 효율적으로 구할 수 있다.

아이디어

1) 완탐 -> O(4^n*n) -> 4가지 방향의 백트레킹은 4가지 방향에 대한 모든 경우를 고려해야 하기 때문에 다음과 같은 시간복잡도를 가지낟.
-> 시간이 오래 걸린다.

2) bfs -> O(N*N) -> 근데 최단 경로 문제가 아니기 때문에 사용할 수 없다.

2) dp -> O(N*N) -> dp로 풀려면 왼쪽 혹은 밑으로 이동 조건이 필요하다.
-> 문제에 적합하지 않다.

3) 그래프 탐색 -> O(NN log(NN)) -> 다익스트라(비용)

다익스트라란?

1) dp 격자를 만든다.
2) 한 장소를 방문하면, 이동가능한 노드를 추가한다.
3) 더 효율적인 거리가 나왔을 때, 갱신해 주고, 힙에 추가한다.
4) 모든 노드를 방문할 때까지 반복한다.

기억 해야하는 문법

heapq.heappush(list,[])
heapq.heappop(list)

실수 포인트

can_go(num+graph[nx][ny], nx, ny)
이전에 graph[nx][ny] 인덱스 범위를 확인해주어야 한다.

코드

import heapq

n = -1
graph = []
dp = []

dxy = [[1,0],[-1,0],[0,1],[0,-1]]

def in_range(x,y):
    return 0 <= x and x < n and 0 <= y and y < n

def can_go(num, x,y):
    if dp[x][y] <= num:
        return False
    return True

def find_min_cost():
    heap = []
    heapq.heappush(heap,[graph[0][0],0,0])

    while heap:
        num, x, y = heapq.heappop(heap)

        for k in range(4):
            nx, ny = x + dxy[k][0], y + dxy[k][1]
            if not in_range(nx, ny):
                continue

            if not can_go(num + graph[nx][ny], nx, ny):
                continue

            dp[nx][ny] = num + graph[nx][ny]
            heapq.heappush(heap, [dp[nx][ny],nx,ny])
        
    return

count = 0
while True:
    n = int(input())
    count += 1
    
    if n == 0:
        break

    graph = [
        list(map(int, input().split()))
        for _ in range(n)
    ]

    dp = [[float("INF")]*n for _ in range(n)]
    find_min_cost()
    print("Problem %d: %d" %(count,dp[n-1][n-1]))

아직 풀리지 않은 문제

## 1번
def can_go(num, x,y):
    if dp[x][y] <= num:
        return False
    return True
    
## 2번
def can_go(num, x,y):
    if dp[x][y] < num:
        return False
    return True

2번의 경우는 시간초과가 난다..
다익스트라의 경우는 큰 경우만 갱신해주는 것이 가장 효율적이다...!