[백준] 4485번 녹색 옷 입은 애가 젤다지?(다익스트라 알고리즘)(Python - 파이썬)

백준 4485번 문제입니다. (solved.ac)기준 골드 4 문제입니다.

문제 접근

링크는 잃는 비용을 최소로 만들어 동굴을 탈출해야합니다. ([0][0] 부터 [n-1][n-1]까지 이동)

잃는 비용을 경로의 길이라고 생각하고 최단 경로를 찾는 방식으로 접근하였습니다.

graph 에 이차원 리스트로 동굴 정보를 입력받고 최단 경로 또한 이차원 리스트에 INF( int(1e9) ) 로 초기화 해줍니다.

그 후 상,하,좌,우 탐색하면서 각 distance에 최단 경로(잃는 루피의 최소 금액)을 갱신하여 주면 됩니다.

예를 들어 distance[3][3]은 0,0부터 3,3으로 가는 최단 경로가 저장 됩니다.

 

0,0에서 시작하기 때문에 distance[0][0]의 값은 graph[0][0]으로 초기화 해줍니다.

distance[0][0] = graph[0][0]

그 후 q에 dis( x, y 좌표로 이동하는 최소 경로), x, y(각각 탐색을 시작하는 지점의 x, y좌표)를 저장합니다.

q = [(graph[0][0], 0, 0)]

우선 순위 큐를 사용하여 q가 빌 때 까지 다익스트라 알고리즘을 통하여 최단 경로를 갱신하여 distance에 저장해줍니다.

    while q:

        # dis에는 graph[x][y]까지의 최단 경로가 저장
        # x, y에는 각각 탐색을 시작하는 지점의 x, y좌표가 저장
        dis, x, y = heapq.heappop(q)

        # 현재 노드와 연결된 다른 인접한 노드들을 확인(상, 하, 좌, 우)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위를 벗어나면 탐색 종료
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue


            # 최단 경로를 갱신
            cost = dis + graph[nx][ny]

            if distance[nx][ny] > cost:
                distance[nx][ny] = cost
                heapq.heappush(q, (cost, nx, ny))

마지막으로 문제의 출력형식에 맞게 출력해주면 됩니다.

print("Problem " + str(cnt) + ": " + str(distance[n - 1][n - 1]))

cnt는 반복문이 돌 때 마다 1씩 증가하도록 하였습니다.(정답 코드 참고)

정답 코드

import heapq
import sys

INF = int(1e9)

cnt = 0
# 상하좌우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while True:
    cnt += 1
    # 동굴의 크기를 입력 받음(n)
    n = int(sys.stdin.readline().rstrip())

    # n이 0이라면 반복문을 탈출
    if n == 0: break

    # 최단 경로를 초기화(이차원 리스트)
    distance = [[INF] * n for _ in range(n)]

    # 동굴 정보를 입력 받음
    graph = [list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(n)]

    # 0,0은 무조건 거쳐야 함.
    distance[0][0] = graph[0][0]

    q = [(graph[0][0], 0, 0)]

    while q:

        # dis에는 graph[x][y]까지의 최단 경로가 저장
        # x, y에는 각각 탐색을 시작하는 지점의 x, y좌표가 저장
        dis, x, y = heapq.heappop(q)

        # 현재 노드와 연결된 다른 인접한 노드들을 확인(상, 하, 좌, 우)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위를 벗어나면 탐색 종료
            if nx < 0 or ny < 0 or nx >= n or ny >= n:
                continue

            # 최단 경로를 갱신
            cost = dis + graph[nx][ny]

            if distance[nx][ny] > cost:
                distance[nx][ny] = cost
                heapq.heappush(q, (cost, nx, ny))

    # 문제 형식에 맞게 출력
    print("Problem " + str(cnt) + ": " + str(distance[n - 1][n - 1]))