[BOJ] 4485번 녹색 옷 입은 애가 젤다지? / 사용언어 : 파이썬(python)

※ 문제링크

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

해당 문제는 다익스트라 알고리즘으로 사용하여 해결 가능한 문제였다. 다익스트라를 구현하기 위해 파이썬의 heapq을 사용하였고,그 외에는 다른 BFS문제와 같은 형태로 로직을 구성하여 구현하였다. 자세한 풀이방법과 코드는 아래와 같다.

1. 지정된 조건이 나올때까지 반복루프를 돌 수 있게 작성하고 입력값들을 바탕으로 동굴을 갱신하여 저장한다.

2. heapq와 리스트를 활용하여 다익스트라 알고리즘을 구현하고 return값을 최저비용으로 주어 출력한다.

3. f-string을 활용하여 문제의 출력조건에 맞게 결과문을 출력한다. + 시간 및 메모리 절감을 위해 sys를 사용하였습니다.

 

from heapq import heappush, heappop
import sys

def dijkstra(cave, N):
    visited = [[False for _ in range(N)] for _ in range(N)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    heap = []
    heappush(heap, [0, 0, -1])

    while heap:
        cost1, x, y = heappop(heap)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                if nx == N-1 and ny == N-1:
                    cost2 = cave[ny][nx]
                    return cost1 + cost2
                elif visited[ny][nx] == False:
                    visited[ny][nx] = True
                    cost2 = cave[ny][nx]
                    heappush(heap, [cost1+cost2, nx, ny])

# input = sys.stdin.readline
cnt = 0
while True:
    cnt += 1
    N = int(input())
    if N == 0:
        break
    cave = []
    for _ in range(N):
        cave.append(list(map(int, input().split())))
    print(f'Problem {cnt}: {dijkstra(cave, N)}')

 

P.S 개발자가 되기위해 공부중입니다. 잘못된 부분을 댓글로 남겨주시면 학습하는데 큰 도움이 될 거 같습니다.