4485. 녹색 옷 입은 애가 젤다지? (다익스트라/데이크스트라) [BAEKJOON / Python]

문제

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

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

 

input = 
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


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

 

전체 코드

# 녹색 옷 입은 애가 젤다지?

from heapq import heappop, heappush
import sys

MAX = sys.maxsize
cnt = 0

# 입력값(n)이 0이 나올 때 까지 반복
while True:
    n = int(input())
    
    if n == 0:
        break
    
    maps = [list(map(int, input().split())) for _ in range(n)]
    visited = [[MAX] * n for _ in range(n)]

    heap = []
    heappush(heap, (maps[0][0], 0, 0))  # 시작 좌표의 값과 좌표를 heap에 할당한다. (5, 0, 0) => rupee값을 맨 앞에 두어야 heap 정렬 시 rupee 기준으로 오름차순 정렬!
    visited[0][0] = maps[0][0]          # 시작 좌표의 값을 방문 리스트에 할당한다.

    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    cnt += 1
    
    while heap:
        rupee, x, y = heappop(heap)
        
        # 현재 위치의 좌표값이 더해온 값보다 작으므로 
        if visited[x][y] < rupee:
            continue
        
        # (n, n)에 도착하면 중단
        if (x, y) == (n - 1, n - 1):
            print(f'Problem {cnt}: {rupee}')
            break
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < n:
                # 4방향 탐색한 위치의 좌표값과 현재위치의 좌표값을 더해서 할당한다.
                n_rupee = rupee + maps[nx][ny]
                
                # 탐색한 좌표값과 현재위치 좌표값을 더한 값이 탐색한 좌표의 값보다 작을 때(최대수보다 작을 때)
                if visited[nx][ny] > n_rupee:   
                    visited[nx][ny] = n_rupee   # 탐색 좌표값 + 현재 좌표값을 방문한 좌표에 할당
                    heappush(heap, (n_rupee, nx, ny))

 

 

문제 풀이 포인트

• heap
  • heap을 사용하여 최소값을 찾는다.
• BFS와 같이 4방향 탐색

 

 

로직

1. 최대값을 설정한다.
2. 방문리스트 생성 시 최대값으로 이루어진 리스트를 생성한다.
3. 4방향 탐색 시 탐색한 좌표의 값과 현재 위치 + 최소 좌표의 값들 로 연산한 값과 비교하여 최소금액으로 (n, n)까지 이동할 수 있는 경우를 찾는다.

 

 

코드 디테일

최대값 설정

from heapq import heappop, heappush
import sys
input = sys.stdin.readline

MAX = sys.maxsize
cnt = 0

sys.maxsize로 최댓값을 설정한다.

 

❓ 최댓값 설정 이유

탐색하며 최솟값을 새롭게 갱신하면서 점점 작은 수로 만들어 가는 것이다.

 

cnt는 정답 출력 시 테스트 케이스의 번호를 출력하기 위함이다.

 

 

heap 설정 및 탐색 시작

while True:
    n = int(input())
    
    if n == 0:
        break
    
    maps = [list(map(int, input().rstrip().split())) for _ in range(n)]
    visited = [[MAX] * n for _ in range(n)]

    heap = []
    heappush(heap, (maps[0][0], 0, 0))  # 시작 좌표의 값과 좌표를 heap에 할당한다. (5, 0, 0) => rupee값을 맨 앞에 두어야 heap 정렬 시 rupee 기준으로 오름차순 정렬!
    visited[0][0] = maps[0][0]          # 시작 좌표의 값을 방문 리스트에 할당한다.

    dx = [0, 0, -1, 1]
    dy = [1, -1, 0, 0]

    cnt += 1

while True문을 사용하여 입력값에 0이 나올때 까지 구문을 반복해준다. (if n == 0: break)

 

방문리스트를 생성할 때 MAX변수 (최댓값)으로 이루어진 리스트를 만들어주도록 한다.

 

❓ 좌표가 아닌 좌표값이 heap 맨 앞에 할당되는 이유

heap 변수에 값을 넣을 때 현재 좌표값 (이동 시 드는 비용)이 맨 앞으로 할당되어야 한다.

그 이유는, 좌표값(비용)을 기준으로 heap이 오름차순 정렬을 하기 때문이다. 

즉, 비용을 맨 앞으로 할당하여 최솟값을 heappop으로 뽑아내어 4방향 탐색하려는 것이다.

 

 

최소비용 탐색 

    while heap:
        rupee, x, y = heappop(heap)
        
        # 현재 위치의 좌표값이 더해온 값보다 작으므로 
        if visited[x][y] < rupee:
            continue
        
        # (n, n)에 도착하면 중단
        if (x, y) == (n - 1, n - 1):
            print(f'Problem {cnt}: {rupee}')
            break
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < n:
                # 4방향 탐색한 위치의 좌표값과 현재위치의 좌표값을 더해서 할당한다.
                n_rupee = rupee + maps[nx][ny]
                
                # 탐색한 좌표값과 현재위치 좌표값을 더한 값이 탐색한 좌표의 값보다 작을 때(최대수보다 작을 때)
                if visited[nx][ny] > n_rupee:   
                    visited[nx][ny] = n_rupee   # 탐색 좌표값 + 현재 좌표값을 방문한 좌표에 할당
                    heappush(heap, (n_rupee, nx, ny))

현재 위치를 heap에서 차례대로 rupee, x, y 변수에 할당한다.

 

        rupee, x, y = heappop(heap)

이 구문에서 heap의 기능으로 인해 자동으로 최솟값을 지닌 길로 이동하게 된다.

만약에

input =
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

이러한 입력값이 주어졌을 때

 

이러한 그래프와 방문 리스트가 생성된다. 최댓값으로 설정한 값은 9223372036854775807 이다.

 

시작점인 (0, 0), 3에서 탐색을 시작하게 된다.

현재 위치인 3에서 오른쪽에 위치한 7과 아래에 위치한 2를 방문한다.

 

그렇다면 이러한 방문 리스트가 갱신된다. 

즉, 현재 위치인 3과 방문한 값 각각 7과 2를 더해주었기 때문에 누적된 최솟값이 방문 리스트에 기록되는 것이다.

 

 

heappop()을 통해 현재 위치인 x, y값을 받게 되는데 이때 (10, 0, 1)이 아닌 (5, 1, 0)의 값으로 받게 된다.

앞서 말했듯이, 최솟값 (10, 5)을 기준으로 heap 정렬을 해주기 때문에 10보다 더 작은 5가 할당되는 것이다.

 

        if visited[x][y] < rupee:
            continue

현재위치의 방문 리스트의 좌표값이 최소비용을 모두 더한 값(rupee)보다 작을 경우에만 실행하도록 한다.

즉, 최소비용을 더해온 값(rupee)보다 방문한 리스트의 현재 위치 값이 더 클 경우는 최소비용을 고려하지 않는 길이므로 아래 구문을 실행시키지 않도록 하는 것이다.

 

 

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            
            if 0 <= nx < n and 0 <= ny < n:
                # 4방향 탐색한 위치의 좌표값과 현재위치의 좌표값을 더해서 할당한다.
                n_rupee = rupee + maps[nx][ny]
                
                # 탐색한 좌표값과 현재위치 좌표값을 더한 값이 탐색한 좌표의 값보다 작을 때(최대수보다 작을 때)
                if visited[nx][ny] > n_rupee:   
                    visited[nx][ny] = n_rupee   # 탐색 좌표값 + 현재 좌표값을 방문한 좌표에 할당
                    heappush(heap, (n_rupee, nx, ny))

4방향을 탐색하며 최소비용을 n_rupee에 누적한다.

 

방문리스트에서 누적 최소 비용이 탐색한 좌표값보다 작을 경우에만 그 값을 할당해준다.