[백준] 등산(1486) 파이썬 풀이

※ 사용언어 : 파이썬 ※

 

▼ 문제 링크 ▼

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

 

---

 

 

문제 접근

◇ 문제에서 요구하는 조건이 많은 편이다. 조건들을 간략하게 정리하면 다음과 같다.

1. 산의 지도(M)에 적힌 높이값은 "A-Z", "a-z" 로 구성. 해당 값을 숫자로 치환시, A-Z == 0-25 / a-z == 26-51

2. 상하좌우 이동하나, 높이 차이가 T 이하여야 함

3. 높이가 높은 곳 → 낮은 곳 => 이동시간 1초 / 높이가 낮은 곳 → 높은 곳 => 이동시간 (낮은 곳 - 높은 곳)^2

4. 해가 지기 전(D)에 시작 시점인 (0,0)으로 다시 돌아와야함.

 

◇ 모든 조건을 만족하면서 세준이가 갈 수 있는 최고 높이를 출력해야하는 문제이다.

 

---

문제 풀이 (With Python)

◇ 전체적인 코드의 흐름을 작성한다면 다음과 같습니다.

1. 위에서 서술한 조건 중 1~3번을 만족하는 좌표값들 다익스트라 알고리즘을 사용해 찾기

2. 찾은 좌표값 중 등산 시간이 D 미만인 좌표값을, heapque에 넣음 (이때 정렬 조건은 가장 높은 높이 부터.)

3. heapque에 들어간 좌표 값 중 조건 4번을 만족하는 값을 찾기

import heapq
import sys

N, M, T, D = map(int, sys.stdin.readline().split())

mountain = []
for _ in range(N):
    mountain.append(list(sys.stdin.readline().rstrip()))

# 1번 조건
for a in range(N):
    for b in range(M):
        if mountain[a][b].isupper():
            mountain[a][b] = ord(mountain[a][b]) - ord("A")
        else:
            mountain[a][b] = (ord(mountain[a][b]) - ord("a")) + 26


dx = [-1,1,0,0]
dy = [0,0,-1,1]
def Dijkstra(sx, sy):
    time = [[int(1e9) for _ in range(M)] for _ in range(N)]
    time[sx][sy] = 0

    que = []
    heapq.heappush(que, [0, sx, sy])
    while que:
        c_time, cx, cy = heapq.heappop(que)
        if time[cx][cy] >= c_time:
            c_height = mountain[cx][cy]
            for i in range(4):
                nx = cx + dx[i]
                ny = cy + dy[i]
                if 0 <= nx < N and 0 <= ny < M:
                    n_height = mountain[nx][ny]
                    # 2번 조건
                    if abs(c_height - n_height) <= T:
                    	# 3번 조건
                        if c_height >= n_height:
                            n_time = c_time + 1
                        else:
                            n_time = c_time + (c_height - n_height) ** 2
						
                        if time[nx][ny] > n_time:
                            time[nx][ny] = n_time
                            heapq.heappush(que, [n_time, nx, ny])
    return time

# 조건을 만족하는 좌표값들 찾기
check_time = Dijkstra(0, 0)

candi = []
for i in range(N):
    for j in range(M):
        if check_time[i][j] < D:
            # 파이썬은 최소 heap만 제공해서 -1을 곱해야 최대 힙을 만들 수 있음
            m_height = -1 * mountain[i][j]
            heapq.heappush(candi, [m_height, i, j])

# 후보 좌표들 중 4번 조건을 만족하는 좌표 찾기
while candi:
    pt, px, py = heapq.heappop(candi)
    possible_time = Dijkstra(px, py)
    # check_time: 0,0 -> px,py
    # possible_time: px,py -> 0,0
    if check_time[px][py] + possible_time[0][0] <= D:
        print(mountain[px][py])
        break

 

◇ 높이 계산을 편히 하기 위해, 본격적인 탐색에 들어가기에 앞서 알파벳 값을 조건에 맞는 숫자값으로 치환 (이 때, 아스키 코드상 대문자 Z 다음 바로 소문자 a가 시작하지 않기 때문에 대소문자를 구분하여 값을 매핑해줌)

 

◇ Dijkstra 함수 안의 time 배열을 선언하여 각 좌표에 도달할 수 있는 여러 시간대 중 최소값을 저장해줍니다.

 

◇ Dijkstra 함수 안의 while문에서 상하좌우로 움직이기 전, 해당 좌표값의 시간값이 time 배열에 저장된 것 보다 작거나 같은 경우만 순회합니다. (time 배열이 DFS와 DFS에서 사용되는 visited배열 역할을 담당)