BOJ 백준 4485번, 녹색 옷 입은 애가 젤다지? - Python 파이썬

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

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

요새 젤다의 전설 왕국의 눈물 재밌게 하고 있는데 이런 문제가 있어서 냉큼 풀어보게 되었다.ㅎㅎ

 

 

이 문제는 BFS나 다익스트라(테이크스트라)로 풀 수 있는데, 다익스트라에 익숙하지 않아서 처음에는 BFS와 섞어서 문제를 풀게 되었다.

# 첫번째 제출 코드
import sys
from collections import deque
input = sys.stdin.readline
INF = int(1e9)
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
tc = 1

while True:
    n = int(input().rstrip())
    if n == 0:  # 테스트 케이스 끝
        break
    graph = [list(map(int, input().rstrip().split())) for _ in range(n)]
    distance = [[INF] * n for _ in range(n)]

    def bfs(a, b):
        q = deque()
        q.append((a, b))
        if a == 0 and b == 0:  # 최초 한번만 돌게 해준다.
            distance[0][0] = graph[0][0]

        while q:
            x, y = q.popleft()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 0 or nx >= n or ny < 0 or ny >= n:  # 범위 초과
                    continue
                cost = graph[nx][ny] + distance[x][y]
                if distance[nx][ny] > cost:  # 최소 거리 갱신해야 한다면
                    distance[nx][ny] = cost
                    q.append((nx, ny))


    for i in range(n):
        for j in range(n):
            if distance[i][j] == INF:
                bfs(i, j)

    print(f"Problem {tc}: {distance[n-1][n-1]}")
    tc += 1

제출 결과

맞추긴 했지만 여러모로 아쉬운 풀이여서 시간을 줄이고, 다익스트라를 사용하도록 리팩토링 했다.

 

 

# 두번째 제출 코드
import sys
import heapq
input = sys.stdin.readline
INF = int(1e9)
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
tc = 1

def dijkstra():
    q = []
    distance[0][0] = graph[0][0]
    # 거리, x좌표, y좌표
    heapq.heappush(q, (distance[0][0], 0, 0))  # 맨 앞의 값(거리)을 기준으로 정렬

    while q:
        dist, x, y = heapq.heappop(q)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx < 0 or nx >= n or ny < 0 or ny >= n:  # 범위 초과
                continue
            cost = dist + graph[nx][ny]
            if distance[nx][ny] > cost:  # 최소 거리 갱신해야 한다면
                distance[nx][ny] = cost
                heapq.heappush(q, (cost, nx, ny))

# 다익스트라 시작
while True:
    n = int(input().rstrip())
    if n == 0:  # 테스트 케이스 끝
        break
    graph = [list(map(int, input().rstrip().split())) for _ in range(n)]
    distance = [[INF] * n for _ in range(n)]

    dijkstra()
    print(f"Problem {tc}: {distance[n-1][n-1]}")
    tc += 1

제출 결과

 

개선1 (시간 단축)

(0, 0)부터 (n-1, n-1)로 가는데 방문하지 못하는 노드는 없기 때문에(ex. 방해물) dijkstra() 함수를 한번만 호출해도 모든 노드(동굴 전체)를 돌게 된다.

따라서 방문하지 않은 노드를 탐색하는 2중 for문을 제거했다.

개선2 (deque 대신 priority queue 사용)

priority queue(heapq)를 이용하면 min-heap(거리)으로 정렬이 되기 때문에, 현재 노드로부터 다음 노드까지의 최단 거리가 먼저 pop()된다.
이후에 오는 거리는 모두 min-heap 보다 크기 때문에 최단 거리가 아니게 되어 24번째 줄에서 걸러진다.