[파이썬] 백준 1486 : 등산 (골드2)

[파이썬] 백준 1486 : 등산 (골드2)

1486번: 등산

---

문제

---

풀이

0. 방향성 생각

• 출발점에서 다익스트라 돌려서 제한시간 넘는 곳 제외한 후, 높은 곳 부터 다시 다익스트라 돌리기.

1. 입력

from collections import defaultdict as dd
import heapq as hq
import sys
input = lambda: sys.stdin.readline().rstrip()

inf = 10**6
table = {}
for i in range(65,91): table[chr(i)] = i-65
for i in range(97,123): table[chr(i)] = i-97+26

h,w,diff,limit = map(int,input().split())
arr = [[] for _ in range(h)]
for i in range(h):
    for j in input():
        arr[i].append(table[j])

• 높이정보 바꿔서 arr에 저장해주기.

2. 높이,간선 정보 정리

for i in range(h):
    for j in range(w):
        height_info[arr[i][j]].append((j,i))

        for d in range(4):
            dj,di = dire[d]
            nj = j + dj
            ni = i + di

            if 0<=nj<w and 0<=ni<h:
                dh = arr[ni][nj] - arr[i][j]
                if abs(dh) <= diff:
                    costs[ni][nj][d] = dh**2 if dh>0 else 1

height_info = list(height_info.items())
height_info.sort(reverse=True)

• height_info에는 높이별로 좌표 정리
• costs에는 현재 노드로 들어오는 방향에 따른 cost 정리

3. 함수 정의

def di(sx,sy):

    visit = [[inf]*w for _ in range(h)]
    visit[sy][sx] = 0
    heap = [(0,sx,sy)]

    while heap:

        t,x,y = hq.heappop(heap)

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

            if 0<=nx<w and 0<=ny<h:
                nt = t + costs[ny][nx][d]
                if nt <= limit and nt < visit[ny][nx]:
                    visit[ny][nx] = nt
                    hq.heappush(heap,(nt,nx,ny))
    return visit

• 출발점에서 시작해서 다익스트라 돌리기.
• visit에는 도달하는 cost정보가 담겨있다.

4. 결과 출력

go = di(0,0)
flag = False
for hei,locs in height_info:
    for j,i in locs:
        if go[i][j] != inf:
            back = di(j,i)
            if go[i][j] + back[0][0] <= limit:
                flag = True
                break
    if flag:
        print(hei)
        break

• 높은 곳 부터 좌표를 받아서, 올라갈 수 있는 노드면 내려가는 다익스트라 실행한다.
• 한 높이에서 하나라도 도달 가능하면 정답이므로 flag만들어서 탈출해주기.

---

전체코드

from collections import defaultdict as dd
import heapq as hq
import sys
input = lambda: sys.stdin.readline().rstrip()

inf = 10**6
table = {}
for i in range(65,91): table[chr(i)] = i-65
for i in range(97,123): table[chr(i)] = i-97+26

h,w,diff,limit = map(int,input().split())
arr = [[] for _ in range(h)]
for i in range(h):
    for j in input():
        arr[i].append(table[j])

dire = [(1,0),(0,1),(-1,0),(0,-1)]
costs = [[[inf]*4 for _ in range(w)] for _ in range(h)]
height_info = dd(list)

for i in range(h):
    for j in range(w):
        height_info[arr[i][j]].append((j,i))

        for d in range(4):
            dj,di = dire[d]
            nj = j + dj
            ni = i + di

            if 0<=nj<w and 0<=ni<h:
                dh = arr[ni][nj] - arr[i][j]
                if abs(dh) <= diff:
                    costs[ni][nj][d] = dh**2 if dh>0 else 1

height_info = list(height_info.items())
height_info.sort(reverse=True)

def di(sx,sy):

    visit = [[inf]*w for _ in range(h)]
    visit[sy][sx] = 0
    heap = [(0,sx,sy)]

    while heap:

        t,x,y = hq.heappop(heap)

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

            if 0<=nx<w and 0<=ny<h:
                nt = t + costs[ny][nx][d]
                if nt <= limit and nt < visit[ny][nx]:
                    visit[ny][nx] = nt
                    hq.heappush(heap,(nt,nx,ny))
    return visit

go = di(0,0)
flag = False
for hei,locs in height_info:
    for j,i in locs:
        if go[i][j] != inf:
            back = di(j,i)
            if go[i][j] + back[0][0] <= limit:
                flag = True
                break
    if flag:
        print(hei)
        break

 

코멘트

아무리 생각해도 시간초과, 메모리초과 날 수가 없는 문제였는데 계속 실패......

디버깅하다가 메모리 초과에 루프탈출 못하는 케이스가 생겨서 매의 눈으로 보다가 등호 하나 넣어버려서 틀렸던거 찾음...

덕분에 코드 깎으면서, 메모리랑 시간줄이는 여러 방법 시도했는데 도움은 된듯