<aside> 🔥 백준 4485번 문제

</aside>

<aside> 🔥 문제

젤다가 n x n크기의 동굴에 들어왔다.

각 동굴에 다음 칸으로 가면 지정된 금액만큼 돈을 잃는다.

[0][0]에서 출발해서 [n-1][n-1]로 갈 때, 최소로 잃는 금액은 얼마일까?

첫째줄에 n이 주어진다. n : 동굴의 크기

다음 n개의 줄에 각 동굴의 칸마다 잃는 금액이 적혀있다.

입력은 여러 케이스로 이루어져있고 n에 0이 입력되면 종료한다.

아래 예제에 출력값 형태에 맞게 출력하자.

</aside>

<aside> 🔥 예제

# 입력값
3
5 5 4
3 9 1
3 2 7
5
3 7 2 0 1
2 8 0 9 1
1 2 1 8 1
9 8 9 2 0
3 6 5 1 5
7
9 0 5 1 1 5 3
4 1 2 1 6 5 3
0 7 6 1 6 8 5
1 1 7 8 3 2 3
9 4 0 7 6 4 1
5 8 3 2 4 8 3
7 4 8 4 8 3 4
0

# 출력값
Problem 1: 20
Problem 2: 19
Problem 3: 36

</aside>

<aside> 🔥 접근 방법

이 문제는 2차원 그래프에서 최단 거리를 찾는 문제이다. 즉 다익스트라 알고리즘을 사용해서

2차원 그래프의 비용 테이블을 계산하고 최종인 [n-1][n-1]의 값이 얼마인지 출력하는 문제이다.

이전에 dfs에 섬의 개수와 비슷하게 인접 좌표를 상하좌우로 탐색해나가면 될거같다.

위 예시 중 첫번째 3 x 3의 경우

</aside>

<aside> 🔥 코드 진행

count를 생성해 반복 횟수마다 증가시켜 출력값에 쓴다.

입력값을 받아주고 n에 0이 입력되었을 때 중지하도록 해준다.

그래프를 생성하고, 상하좌우 탐색에 쓰일 테이블을 생성해준다.

마지막줄에 count와 다익스트라 함수의 반환값으로 출력한다.

count = 0
while True:
    count += 1
    n = int(input())

    if n == 0:
        break

    cave_map = [list(map(int, input().split())) for _ in range(n)]

    # 상하좌우 테이블
    dx = [0, 0, -1, 1]
    dy = [-1, 1, 0, 0]

		print(f"Problem {count}: {dijkstra(cave_map, 0, 0)}")

다익스트라 알고리즘을 작성한다.

루피 테이블을 생성해주고 힙을 생성해서 힙에 (비용, x좌표, y좌표)를 넣어준다.

def dijkstra(cave_map, x, y):
    # 무한 지정
    INF = int(1e9)

    # 루피 테이블 생성
    ruppe_table = [[INF] * n for _ in range(n)]

    # 힙 생성
    q = []
    # 힙에 (잃는 루피의 값, x좌표, y좌표) 넣어주기
    heapq.heappush(q, (cave_map[0][0], x, y))

    # 시작점 잃는 루피 추가.
    ruppe_table[0][0] = cave_map[0][0]

상하좌우를 탐색해서 테이블을 갱신시켜준다.

# q가 있는동안 반복
    while q:
        # 최소 누적 루피 금액과 좌표를 꺼내온다.
        acc, x, y = heapq.heappop(q)

        # 루피 테이블에 이미 누적값보다 작은게 들어있으면 skip
        if ruppe_table[x][y] < acc:
            continue

        # 상하좌우 탐색 시작
        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 = acc + cave_map[nx][ny]
            # 누적 루피가 기록된곳보다 더 작으면
            if cost < ruppe_table[nx][ny] :
                # 업데이트
                ruppe_table[nx][ny] = cost
                # 힙에 넣기
                heapq.heappush(q, (cost, nx, ny))
    # 마지막 지점에 도달했을때 최소값 리턴
    return ruppe_table[-1][-1]

</aside>