[BOJ] 1486 등산

def checkheight(alp):
    if alp.isupper():
        return ord(alp) - ord('A')
    else:
        return ord(alp)-ord('a')+26

def custom_minus(a,b,flag):
    if flag:
        return a - b
    else:
        return b - a

def solve(timeslist,flag):
    global N,M,T
    dx = [-1,1,0,0]
    dy = [0,0,1,-1]
    total = 0
    visited = [[True] * M for _ in range(N)]
    x = 0
    y = 0
    timeslist[0][0] = 0
    while total <N*M:
        visited[x][y] = False
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx< N and 0 <= ny <M:
                gap = custom_minus(arr[x][y],arr[nx][ny],flag)
                if abs(gap) <= T:
                    if gap < 0:
                        time_temp = abs(gap)**2
                        
                    else:
                        time_temp = 1
                    timeslist[nx][ny] = min(timeslist[nx][ny],timeslist[x][y]+time_temp)
        next_node_x = -1
        next_node_y = -1
        next_times = INF
        for i in range(N):
            for j in range(M):
                if visited[i][j] and next_times > timeslist[i][j]:
                    next_times = timeslist[i][j]
                    next_node_x = i
                    next_node_y = j
        x = next_node_x
        y = next_node_y
        total += 1
        if next_times == INF:
            break

        



N,M,T,D = map(int,input().split())
arr = [list(map(checkheight,list(input()))) for _ in range(N)]
INF =float('inf')

times = [[INF]*M for _ in range(N)]
reversed_times = [[INF]*M for _ in range(N)]
solve(times,True)
solve(reversed_times,False)
max_height = arr[0][0]

for i in range(N):
    for j in range(M):
        if times[i][j] + reversed_times[i][j] <= D and max_height < arr[i][j]:
            max_height = arr[i][j]
print(max_height)

이 문제는 다익스트라 알고리즘을 이용해서 푼 문제이다.

ord라는 함수를 통해, 알파벳을 문제에 주어진 숫자로 변경시켜주었다.

이 문제는 처음에 냈을때 틀렸는데, 그 이유는, 문제를 제대로 읽지 않고, 해당 목적지까지 정해진 시간 D 까지만 가면 되는 줄 알았는데, 처음 호텔위치로 돌아와야했다.

 

이 문제는 단순히 다익스트라를 두번 돌리면 된다.

출발지와 목적지까지 올라가는 다익스트라 한번

목적지에서 출발지로 돌아오는 다익스트라 한번

하면된다.

 

이 문제를 두개의 함수로 나뉘어서 하기 싫어서 flag라는 변경점을 주고, 하산할때에는 뺄셈 방식을 반대로 해주게 하여, 하나의 다익스트라를 찾는 함수로 올라갈때와 내려갈때를 구현했다.

 

그리고 문제를 풀고난뒤, 다른사람들 풀이를 보니, 전체 N이 작아서 플로이드 와샬 방법으로 풀어도 된다고 한다.

하지만, 플로이드 와샬이 아직 잘 몰라서 그 방법으로 못 풀어봤다.

 

나중에 기회가 되면 플로이드 와샬로도 풀어볼 예정이다.