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

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

해당문제는 BFS혹은 데이크스트라로 문제를 해결 할 수 있습니다.

BFS는 N이 충분히 작고 가중치가 9이하 이기때문에 시간복잡도 안에 충분히 풀 수 있습니다. 하지만 N이 증가하고, 가중치가 증가한다면 BFS로는 시간복잡도내에 풀 수 없습니다.

해당 문제는 데이크스트라로 문제를 해결하였고, 우선순위 큐를 활용하여 최소 방문거리를 계산 하였습니다.

<aside> 💡 파이썬의 format 함수 : {}, {} 에 변수를 넣을 수 있다. 또한 소수점 개수를 출력하는 format을 사용하고 싶을 경우 {:.2f} 를 하게되면 소수점 자리가 2개 까지 가능하다.

</aside>

move = ((0,1), (1,0), (0,-1), (-1,0))
import heapq
cnt = 1
while True:
    N = int(input())
    if N == 0:
        break

    INF = N*N*9 + 1
    graph = [list(map(int, input().split())) for _ in range(N)]
    queue = []
    visit = [[INF for _ in range(N)] for _ in range(N)]
    visit[0][0] = 0
    heapq.heappush(queue, (graph[0][0], 0 ,0))
    while queue:
        cost, i, j = heapq.heappop(queue)

        if i == N-1 and j == N-1:
            break

        for dy, dx in move:
            ny, nx = dy + i, dx + j
            if N > ny >= 0 and N > nx >= 0 and visit[ny][nx] > cost + graph[ny][nx]: # 거리가 최단거리가 아닐경우 방문한다.
                newcost = cost + graph[ny][nx]
                visit[ny][nx] = newcost
                heapq.heappush(queue, (newcost, ny, nx))

    print("Problem {}: {}".format(cnt, visit[N-1][N-1]))
    cnt += 1