[ BOJ ] 1486 : 등산 ( GOLD 2 ) / Python

문제

세준이는 등산광이다. 세준이는 높은 곳에서 도시를 내려다 보는 것을 좋아한다. 하지만, 겁이 많은 세준이는 어두워지기 전에 호텔로 내려오려고 한다.

세준이가 가려고하는 산의 지도가 입력으로 주어진다. 산의 지도를 M이라고 했을 때, M[i][j]는 (i,j)의 높이가 M[i][j]라는 것을 의미한다. 그 값이 'A'-'Z'일 때는 0-25를 뜻하는 것이고, 'a'-'z'일 때는, 26-51을 뜻한다.

세준이의 호텔은 (0,0)에 있다. 그리고, 세준이는 지금 위치에서 바로 인접한 정수 좌표 중 높이의 차이가 T보다 크지 않은 곳으로만 다닐 수 있다.

만약 세준이가 현재 위치에서 높이가 낮은 곳이나 같은 곳으로 이동한다면 시간은 1초가 걸린다. 하지만 높은 곳으로 이동한다면 두 위치의 높이의 차이의 제곱만큼 시간이 걸린다. 예를 들어 높이가 5에서 높이가 9인 곳으로 간다면, 시간은 (5-9)2=16초가 걸린다. 하지만, 높이가 9인 곳에서 5인 곳으로 간다면 시간은 1초가 걸린다.

산의 지도와, T, 그리고 어두워지는 시간 D가 주어졌을 때, 세준이가 D보다 크지 않은 시간 동안 올라갈 수 있는 최대 높이를 구하는 프로그램을 작성하시오.(세준이는 호텔에서 출발해서 호텔로 돌아와야 한다.)

입력

첫째 줄에 산의 세로크기 N과 가로크기 M 그리고, T와 D가 주어진다. N과 M은 25보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지도가 주어진다. T는 52보다 작거나 같은 자연수이고, D는 1,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 세준이가 갈 수 있는 가장 높은 곳의 높이를 출력한다.

풀이 과정

1. 먼저, (1) 인접한 산길 높이 차이가 T보다 크지 않은지를 판단하기 위함과 (2) 내려갈 때 1초 / 올라갈 때 높이 차이 제곱만큼 시간이 걸리는 가중치를 보기 위해 맵을 전체 탐색하며 전처리하여 그래프로 만들었다.

 

2. 그리고, (0, 0) 좌표에서 진행한 다익스트라와 (i, j) 좌표에서 진행한 다익스트라를 계산하여 (0, 0) -> (i, j) 의 최단거리와 (i, j) -> (0, 0) 의 최단거리의 합을 이용해 출발해서 돌아오는 시간을 쟀다. 

 

3. 이 시간이 d 보다 작거나 같은 위치들 중 최대 높이를 구했다.

import sys
import heapq
input = sys.stdin.readline

n, m, t, d = map(int, input().rstrip().split())
maps = [list(input().rstrip()) for _ in range(n)]

row = [-1, 1, 0, 0]
col = [0, 0, -1, 1]

height = {chr(ord('A')+i):i for i in range(26)}
for i in range(26):
    height[chr(ord('a')+i)] = 26+i

graph = [[{} for _ in range(m)] for _ in range(n)]

for i in range(n):
    for j in range(m):
        for dir in range(4):
            ny = i + row[dir]
            nx = j + col[dir]

            if 0 <= ny < n and 0 <= nx < m:
                now_height = height[maps[i][j]]
                go_height = height[maps[ny][nx]]
                if (abs(now_height - go_height) > t): continue
                if now_height >= go_height:
                    graph[i][j][str(ny)+"_"+str(nx)] = 1 
                else:
                    graph[i][j][str(ny)+"_"+str(nx)] = (now_height - go_height) ** 2
def dijkstra(sy, sx):
    distances = [[float('inf') for _ in range(m)] for _ in range(n)]
    distances[sy][sx] = 0
    queue = []
    heapq.heappush(queue, (0, sy, sx))

    while queue:
        current_distance, current_y, current_x = heapq.heappop(queue)

        if current_distance > distances[current_y][current_x]: continue

        for next_destination, next_distance in graph[current_y][current_x].items():
            ny, nx = map(int, next_destination.split('_'))
            if current_distance + next_distance < distances[ny][nx]:
                distances[ny][nx] = current_distance + next_distance
                heapq.heappush(queue, (current_distance + next_distance, ny, nx))
    
    return distances

result = dijkstra(0, 0)

max_height = height[maps[0][0]]
for i in range(n):
    for j in range(m):
        if i == j == 0: continue
        now_result = dijkstra(i, j)
        if result[i][j] + now_result[0][0] > d: continue
        max_height = max(max_height, height[maps[i][j]])
print(max_height)