[Python][백준 1719] 등산

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

1486번: 등산

---

/*
신경써야 할 부분은 바로 :
1. 입력된 알파벳을 숫자로 변환 (ASCII 코드 응용)
2. 변환한 높이정보를 활용해 상하좌우 오버플로 체크 후 해당 위치까지 가는데 걸리는 시간 계산
	2.1 높이가 출발 위치보다 높으면 둘의 차의 제곱
	2.2 출발 위치보다 낮으면 1
    2.3 행렬 형태로 저장된 값을 리스트 형태로 변형 i*(가로열 길이) + j
3. 얻은 값으로 플로이드 워셜 돌리기
4. 얻은 값을 탐색하며 주어진 시간 안에서 갈 수 있는 가장 높은 곳 출력
*/

---

import sys
input = sys.stdin.readline
 
INF = float('inf')

def floyd(values) :
    global n,m,height,time 
    wasd = [(1,0), (-1,0), (0,1), (0,-1)]
    dist = [[INF for j in range(n*m)] for i in range(n*m)]
    
    for i in range(n) :
        for j in range(m) :
            for k in range(4) :
                if i + wasd[k][0] < 0 or i + wasd[k][0] >= n or j + wasd[k][1] < 0 or j + wasd[k][1] >= m :
                    continue
                if abs(values[i][j] - values[i+wasd[k][0]][j+wasd[k][1]]) > height :
                    dist[i*m + j][(i+wasd[k][0])*m + j+wasd[k][1]] = INF
                elif values[i][j] < values[i+wasd[k][0]][j+wasd[k][1]] :
                    dist[i*m + j][(i+wasd[k][0])*m + j+wasd[k][1]] = pow(values[i+wasd[k][0]][j+wasd[k][1]] - values[i][j],exp=2)
                else :
                    dist[i*m + j][(i+wasd[k][0])*m + j+wasd[k][1]] = 1
    
    for k in range(m*n) :
        for i in range(m*n) :
            for j in range(m*n) :
                dist[i][j] = min(dist[i][j],dist[i][k] + dist[k][j])
    
    return dist

n,m,height,time = map(int, input().split())
graph = [input().strip() for _ in range(n)]
values = [[0 for i in range(m) ] for _ in range(n)]
    
for i in range(n):
    for j in range(m) :
        if graph[i][j].isupper() == True :
            values[i][j] = ord(graph[i][j]) - ord('A')
        else :
            values[i][j] = 26 + ord(graph[i][j]) - ord('a')

floyd_data = floyd(values)

result = values[0][0]
for i in range(1,n*m) : 
    if floyd_data[0][i] + floyd_data[i][0] <= time :
        result = max(result, values[int(i/m)][i%m])

print(result)

---

풀 때 어려웠던 점 또는 느낀점 :

골2 난이도쯤 되니 플로이드 워셜을 돌리기 위해 해야 하는 전처리가 좀 더 복잡해지고

조건도 늘어났다. 도대체 플레 이상급 문제들에선 어떻게 출제되길래..

그래도 막상 다 풀고 나면 이해가 어려운 논리는 아니여서 다행이다.

플로이드 워셜 문제는 여기까지 푸는게 나을 거 같다.

그동안 즐거웠다 플로이드 워셜!

---

참고할만한 다른 사람 코드 :

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

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

def get_height(ch):
    ch = ord(ch)
    if ch >= ord('a'):
        return ch - ord('a') + 26
    else:
        return ch - ord('A')

def dijkstra(compare):
    table = [[float('inf')] * M for _ in range(N)]
    heap = []
    heappush(heap,(0,0,0))
    table[0][0] = 0
    while heap:
        d,x,y = heappop(heap)

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0<=nx<M and 0<=ny<N:
                delta = field[y][x] - field[ny][nx]
                if abs(delta) > T:
                    continue
                nd = d
                if compare(delta):
                    nd += 1
                else:
                    nd += delta ** 2
                
                if table[ny][nx] > nd:
                    table[ny][nx] = nd
                    heappush(heap, (nd, nx, ny))
    return table
N, M, T, D = map(int, input().split())
field = [[0] * M for _ in range(N)]
for y in range(N):
    row = input()
    for x in range(M):
        field[y][x] = get_height(row[x])

ascents = dijkstra(lambda x:x>=0)
descents = dijkstra(lambda x:x<=0)

highest = 0
for y in range(N):
    for x in range(M):
        if ascents[y][x] + descents[y][x] <= D:
            highest = max(highest, field[y][x])

print(highest)

 

다익스트라 풀이

올라가는 최단경로와 내려가는 최단경로를 따로 계산했다.

다익스트라도 익숙해져야 한다.

내일부턴 다익스트라다