[백준(BOJ)] #4485- 녹색 옷 입은 애가 젤다지? (파이썬, PyPy3)

문제

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

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

 

---

문제 풀이

다익스트라 알고리즘의 개념, BFS 알고리즘

2022.07.31 - [PS/알고리즘 이론] - [파이썬으로 배우는 알고리즘] 다익스트라(Dijkstra) 알고리즘

[파이썬으로 배우는 알고리즘] 다익스트라(Dijkstra) 알고리즘

 

1) 인접한 상하좌우의 길의 좌표와 해당 길까지 잃는 소지금을 힙에 push (해당 길까지 잃는 소지금이 적을수록 우선순위가 높음)

2) 힙에서 pop을 하여 잃는 소지금이 제일 적은 길의 좌표를 얻음

3) 1) ~ 2) 과정을 N-1, N-1 좌표로 갈 때 까지 반복

 

---

구현

코드

import sys
import heapq as hq
input = sys.stdin.readline

if __name__ == "__main__":
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    index = 1

    while True:
        N = int(input())
        if N == 0:
            break
        a = [list(map(int, input().split())) for _ in range(N)]
        visited = [[False] * N for _ in range(N)]
        heap = list()
        visited[0][0] = True
        # 잃는 소지금이 적을 수록 우선 순위가 높음
        hq.heappush(heap, (a[0][0], 0, 0))
        while heap:
            cost, tx, ty = hq.heappop(heap)
            # 마지막 좌표에 도달하면 끝
            if tx == N-1 and ty == N-1:
                print("Problem %d: %d" % (index, cost))
                break
            for k in range(4):
                x = tx + dx[k]
                y = ty + dy[k]
                if 0 <= x < N and 0 <= y < N and not visited[x][y]:
                    visited[x][y] = True
                    hq.heappush(heap, (cost + a[x][y], x, y))
        index += 1

결과