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

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

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

 

 

첫 접근은 최단 경로를 구하는 문제라고 생각해서 BFS를 사용했다. 하지만 테스트 케이스조차 통과하지 못하였고 힌트를 얻어 다익스트라 알고리즘을 사용하는 것을 파악했다. 출발지 (0,0)에서 목적지 (n-1, n-1)까지 최단 비용을 사용하여 목적지에 도달해야 한다. 그러기 위해서는 무작정 출발지에서 최소 비용을 따라갈 것이 아니라 지속적인 갱신이 필요하다. 

 

파란색 경로는 갱신 없이 최소 비용만을 따라갔을 때의 비용 = 20

빨간색 경로는 해당 좌표의 최소 비용을 갱신하면서 따라갔을 때의 비용 = 19

 

이와 같이 다익스트라 알고리즘을 사용하면 BFS를 사용한 것 보다 더 적은 비용으로 목적지까지 도달할 수 있다.

내 풀이 : 368ms

import itertools
import sys, heapq
si = sys.stdin.readline
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from math import factorial,sqrt
from itertools import permutations, combinations, accumulate
mn, mx = float('inf'), float('-inf')
dir = [[1,0],[0,1],[0,-1],[-1,0]]
def bfs(a,b,graph,cost) :
    q = deque([])
    q.append((a,b))
    while q :
        x,y=q.popleft()
        for i in range(4):
            nx = x + dir[i][0]
            ny = y + dir[i][1]
            if 0 <= nx < n and 0 <= ny < n :
                if cost[nx][ny] > cost[x][y] + graph[nx][ny] :
                    cost[nx][ny] = cost[x][y] + graph[nx][ny]
                    q.append((nx,ny))

i = 1
while True :
    n = int(si())
    if n == 0 : break
    graph = []
    cost = [[float('inf') for _ in range(n)] for _ in range(n)]
    for _ in range(n) :
        lst = list(map(int, si().split()))
        graph.append(lst)
    cost[0][0] = graph[0][0]
    bfs(0,0,graph,cost)
    print("Problem %d: %d"%(i,cost[n-1][n-1]))
    i += 1

 

여기서 개선된 다익스트라 알고리즘을 사용해보았다. 힙큐(우선순위 큐)를 사용하여 최소 비용순으로 데이터를 꺼내 계산 횟수를 줄였다. 시간이 거의 3배 차이가 나는 것을 볼 수 있다. 

 

heapq를 사용한 풀이 : 132ms

import sys, heapq
si = sys.stdin.readline
from collections import defaultdict, deque, Counter
INF = float('inf')
dir = [[1,0],[0,1],[0,-1],[-1,0]]
def bfs(a,b,c) :
    # q = deque([])
    # q.append((a,b))
    q = [[c, a, b]]
    while q :
        # x,y=q.popleft()
        w, x, y = heapq.heappop(q)
        for i in range(4):
            nx = x + dir[i][0]
            ny = y + dir[i][1]
            if 0 <= nx < n and 0 <= ny < n :
                if cost[nx][ny] > w + graph[nx][ny] :
                    cost[nx][ny] = w + graph[nx][ny]
                    heapq.heappush(q,[cost[nx][ny], nx, ny])

i = 1
while True :
    n = int(si())
    if n == 0 : break
    cost = [[INF for _ in range(n)] for _ in range(n)]
    graph = []
    for _ in range(n) :
        graph.append(list(map(int, si().split())))

    bfs(0,0, graph[0][0])
    print("Problem %d: %d"%(i,cost[n-1][n-1]))
    i += 1
'''
3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4
0
'''