[백준 1486번] 등산 (Python3)

import sys
input = sys.stdin.readline
from heapq import heappush,heappop
INF = sys.maxsize
dy = [1,-1,0,0]
dx = [0,0,1,-1]

def Djikstra(x):
  DP = [INF]*N*M
  hq = []
  heappush(hq,(0,x))

  while hq:
    w,now = heappop(hq)
    if DP[now] <= w:
      continue
    DP[now] = w
    for next,w1 in graph[now]:
      heappush(hq,(w+w1,next))
  return DP[0]

N,M,T,D = map(int,input().split())

MAP = []
for i in range(N):
  MAP.append([*map(lambda x:ord(x)-65 if x.isupper() else ord(x)-71,input().strip())])

graph = [[] for i in range(N*M)]

for y in range(N):
  for x in range(M):
    h = MAP[y][x]
    for i in range(4):
      y1,x1 = y+dy[i],x+dx[i]
      if N>y1>=0 and M>x1>=0:
        h1 = MAP[y1][x1]
        if abs(h-h1) <= T:
          d = 1
          if h1>h:
            d = (h1-h)**2
          graph[y*M+x].append((y1*M+x1,d))
          
DP = [INF]*N*M
hq = []
heappush(hq,(0,0))

while hq:
  w,now = heappop(hq)
  if DP[now] <= w:
    continue
  DP[now] = w
  for next,w1 in graph[now]:
    heappush(hq,(w+w1,next))

highest = []
for i in range(N*M):
  if DP[i] < D:
    highest.append((MAP[i//M][i%M],i))
highest.sort(reverse=True)

for h,i in highest:
  if Djikstra(i)+DP[i] <= D:
    print(h)
    break

풀이는 쉬운데 의외의 실수가 많았던 문제.

 

알고리즘 자체는 매우 쉽다. 그냥 모든 지점에서 인접한 곳으로 갈 수 있으면 그래프를 만들고 다익스트라를 하면 된다.

 

그런데 이제 내가 실수했던 부분은,

1. 호텔로 다시 돌아와야한다는 것을 안읽음

2. 아스키코드에서 소문자는 대문자 바로 다음에 나오는것이 아님

 

이었다.

이 문제는 특이하게 굳이 높이를 숫자가 아니고 알파벳으로 줬는데, 나는 높이로 치환하기 위해서 아스키코드를 이용하였다. 그런데 자꾸 예제의 답이 잘못 나와서 알아보니 아스키코드에서 A~Z 다음에 바로 a가 나오는게 아니라 특수문자가 나온 다음에 a~z가 나온다는 것을 알게되었다.

 

 

오늘의 교훈) 아스키코드에서 소문자는 대문자 바로 다음이 아니다.