백준 1486번 등산

1. 문제 설명

문제 링크

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

세준이가 가려고하는 산의 지도가 입력으로 주어진다. 산의 지도를 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보다 작거나 같은 자연수이다.

출력

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

2. 코드

import sys
from heapq import heappush, heappop

INF = sys.maxsize
input = sys.stdin.readline

class Solution():
    def __init__(self):
        self.n, self.m, self.t, self.d = map(int, input().split())
        self.maps = []
        self.row = []
        self.dx = [0, 0, 1, -1]
        self.dy = [1, -1, 0, 0]
        self.q = []
    def change(self):
        self.row = list(input().rstrip())
        for i in range(self.m):
            k = ord(self.row[i])
            if k >= 97:
                self.row[i] = k - 71
            else:
                self.row[i] = k - 65
        self.maps.append(self.row)

    def dijstra(self, s_x, s_y):
        queue = []
        heappush(queue, (0, s_x, s_y))

        dis = [[INF] * self.m for _ in range(self.n)]
        dis[s_x][s_y] = 0

        while queue:
            dist, x, y = heappop(queue)

            if dis[x][y] < dist:
                continue
            for i in range(4):
                nx = x + self.dx[i]
                ny = y + self.dy[i]

                if 0 <= nx < self.n and 0 <= ny < self.m:
                    g = self.maps[nx][ny] - self.maps[x][y]

                    if abs(g) <= self.t:
                        if g <= 0:
                            time = 1
                        else:
                            time = g ** 2
                        cost = dist + time
                        if cost < dis[nx][ny]:
                            dis[nx][ny] = cost
                            heappush(queue, (cost, nx, ny))
        return dis
    def cal(self, n, m, lst):
        for i in range(n):
            for j in range(m):
                if lst[i][j] <= self.d:
                    heappush(self.q, (-self.maps[i][j], i, j))
        return self.q
    def ans(self, lst, S):
        while lst:
            dist, x, y = heappop(lst)
            E = self.dijstra(x, y)

            if E[0][0] + S[x][y] <= self.d:
                print(self.maps[x][y])
                break

k = Solution()
for _ in range(k.n):
    k.change()
s = k.dijstra(0, 0)
w = k.cal(k.n, k.m, s)
k.ans(w, s)

 

3. 회고

Q. 문제를 보고 든 생각

• 이 문제에서는 목적지에 대해 언급을 하지 않았다.
• 출발지 기준으로 갈수 있는 곳을 다 목적지라고 바라봐야한다
• 목적지에서 다시 호텔로 돌아 가는걸 찾아 가야하며, 문제에서 주어지는 t 값 이내이어야 한다.