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

황준성·2024년 12월 23일

다익스트라 백준

BOJ_Python

목록 보기

47/70

문제

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스의 첫째 줄에는 동굴의 크기를 나타내는 정수 N이 주어진다. (2 ≤ N ≤ 125) N = 0인 입력이 주어지면 전체 입력이 종료된다.

이어서 N개의 줄에 걸쳐 동굴의 각 칸에 있는 도둑루피의 크기가 공백으로 구분되어 차례대로 주어진다. 도둑루피의 크기가 k면 이 칸을 지나면 k루피를 잃는다는 뜻이다. 여기서 주어지는 모든 정수는 0 이상 9 이하인 한 자리 수다.

출력

각 테스트 케이스마다 한 줄에 걸쳐 정답을 형식에 맞춰서 출력한다. 형식은 예제 출력을 참고하시오.

입력 예시 1

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

출력 예시 1

Problem 1: 20
Problem 2: 19
Problem 3: 36

문제 이해

바로 이전에 풀었던 "백준 1261번-알고스팟" 풀이가 비슷한 문제이다. 이전 문제를 풀때 다익스트라 알고리즘을 제대로 이해하지 못하고 있어서 애를 먹었는데 이해를 하니까 시뮬레이션과 합쳐진 문제도 그럭저럭 풀만하다.

그냥 인접 리스트 형태의 다익스트라를 인접 행렬+시뮬래이션으로 푸는 것과 같다.

인접 행렬 + 시뮬레이션으로 다익스트라 구현

시뮬레이션을 합쳐진 문제는 보통 가중치를 리스트에 들어있는 값으로 표현한다.

# 인접 리스트일때
for adj_node, adj_distance in adj_list[cur_node]
	temp_distance = cur_distance + adj_distance # 인접 리스트 가중치 더하기


# 상하좌우로 이동하는 인접 행렬일때
 for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < M and 0 <= ny < N:
            	
                # 인접 행렬에서 가중치 더하기
                temp_distance = cur_distance + adj_matrix[ny][nx]

인접 행렬일때는 윗 코드를 아래 코드로 대체를 한다. 가중치는 보통 행렬의 값이기 때문에 값을 더해주면 된다.

코드

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

# 읽는 속도 효율화
import sys
input = sys.stdin.readline

# Import PriorityQueue
from queue import PriorityQueue

# 방향 벡터 동-서-남-북순
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

# Function Dijkstra Algorithm
def Dijkstra(cur_count, y, x):

    count = [ [INF] * N for _ in range(N)]

    pq = PriorityQueue()
    pq.put([cur_count, y, x]) # 인접 리스트라면 cur_distance, cur_node
    count[y][x] = cur_count # 시작 좌표 값 0

    while not pq.empty():

        cur_count, y, x = pq.get()

        # 인접 행렬 + 시뮬레이션이면 아래 조건문까지가 for adj_node, adj_distance in adj_list[cur_node]를 대신함
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < N and 0 <= ny < N:

                # 원래 있는 값보다 갱신할 값이 더 작으면 갱신
                if cur_count + adj_matrix[ny][nx] < count[ny][nx]:
                    
                    temp_count = cur_count + adj_matrix[ny][nx]
                    count[ny][nx] = temp_count
                    pq.put([temp_count, ny, nx])

    return count

# 0. 전체 반복
INF = int(1e12)
num_count = 0

while True:

    # 1. 입력 및 초기화
    N = int(input())
    num_count += 1

    if N == 0: # 종료 조건
        break

    # 2. Create adj_matrix
    adj_matrix = []
    
    for i in range(N):
        adj_matrix.append(list(map(int, input().split())))

    # 3. Excute Dijlstra Algorithm
    result = Dijkstra(adj_matrix[0][0], 0, 0) # cur_count, 시작 좌표값(0, 0)

    # 4. Print result
    print(f"Problem {num_count}: {result[N-1][N-1]}")