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

JaeYeop·2022년 4월 11일
0

백준

목록 보기
7/19

[문제]

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

[코드]

import sys
import heapq
INF = int(1e9)
input = sys.stdin.readline


result = []
while True:

    n = int(input())
    if n == 0:
        break

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

    def dijkstra():
        heap = []
        distance = []
        for i in range(n):
            distance.append([INF] * n)
        dRow = [0, 0, 1, -1]
        dColumn = [1, -1, 0, 0]

        heapq.heappush(heap, [graph[0][0], 0, 0])
        while heap:
            dist, row, column = heapq.heappop(heap)

            if distance[row][column] < dist:
                continue

            for i in range(4):
                movedRow, movedColumn = row + dRow[i], column + dColumn[i]
                if movedRow < 0 or n <= movedRow or movedColumn < 0 or n <= movedColumn:
                    continue

                cost = dist + graph[movedRow][movedColumn]
                if cost < distance[movedRow][movedColumn]:
                    distance[movedRow][movedColumn] = cost
                    heapq.heappush(heap, [cost, movedRow, movedColumn])

        return distance

    result.append(dijkstra()[n-1][n-1])

for i in range(len(result)):
    print(f'Problem {i+1}: {result[i]}')

[풀이]

이 문제는 다익스트라 알고리즘과 이코테의 2차원 평면 기술을 통해서 쉽게 해결 가능하다

파라미터를 입력받고 다익스트라 메소드 부분에서 dRow와 dColumn을 정의한다
그리고 row, column에서 동서남북으로 이동시 범위를 벗어나지 않는다면 다익스트라 알고리즘을 수행할 수 있게 heap에 넣는다

profile
이게 왜 틀리지... (나의 메모용 블로그)

0개의 댓글