[파이썬, 자바] 백준 16681 : 등산 (골드2)

[파이썬, 자바] 백준 16681 : 등산 (골드2)

• https://www.acmicpc.net/problem/16681

---

풀이

방향성 생각

• 성취감은 높이로 이미 고정되어있다.
• 등산의 가치를 최대로 하려면 소모한 체력을 최소로 해야한다.
• 즉, 이동 거리가 최소여야하는 최단 거리 문제에 노드 간 이동 조건이 붙은 문제.
• 1 -> N -> 1로 이동을 해야하므로 다익 2번 돌리기.
• 1 -> N으로 이동이 가능하다는거 자체가 N -> 1도 가능하다는 소리.
• 처음에는 다익 파라미터에 is_up같은거를 전달해서 조건문에서 다르게 구현하려고 했는데 그럴 필요가 없다.

 

---

파이썬

import heapq as hq
import sys

input = lambda : sys.stdin.readline().rstrip()
INF = float('inf')

N,M,D,E = map(int,input().split())
heights = [None] + list(map(int,input().split()))

G = [[] for _ in range(N+1)]
for _ in range(M):
    a,b,cost = map(int,input().split())
    G[a].append((b,cost))
    G[b].append((a,cost))

def di(sx):
    heap = [(0,sx)]
    V = [INF]*(N+1)
    V[sx] = 0

    while heap:

        t,x = hq.heappop(heap)

        if t > V[x]:
            continue

        for nx,cost in G[x]:
            nt = t+cost
            if heights[x] < heights[nx] and t < V[nx]:
                hq.heappush(heap,(nt,nx))
                V[nx] = nt
    return V

up, down = di(1), di(N)
values = []
for i in range(1,N+1):
    if up[i] == INF or down[i] == INF:
        continue
    values.append(heights[i]*E-(up[i]+down[i])*D)
print(max(values) if values else "Impossible")

---

자바

import java.io.*;
import java.util.*;

public class Main {
    static int N, M, D, E;
    static int[] heights;
    static List<List<int[]>> G;
    static final long INF = Long.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        D = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        heights = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            heights[i] = Integer.parseInt(st.nextToken());
        }

        G = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            G.add(new ArrayList<>());
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            G.get(a).add(new int[]{b, cost});
            G.get(b).add(new int[]{a, cost});
        }

        long[] up = di(1);
        long[] down = di(N);

        long maxVal = -INF;
        for (int i = 1; i <= N; i++) {
            if (up[i] == INF || down[i] == INF) continue;
            maxVal = Math.max(maxVal, heights[i] * (long) E - (up[i] + down[i]) * (long) D);
        }

        System.out.println(maxVal == -INF ? "Impossible" : maxVal);
    }

    static long[] di(int sx) {
        PriorityQueue<long[]> heap = new PriorityQueue<>(Comparator.comparingLong(o -> o[0]));
        long[] V = new long[N + 1];
        Arrays.fill(V, INF);
        V[sx] = 0;
        heap.add(new long[]{0, sx});

        while (!heap.isEmpty()) {
            long[] cinfo = heap.poll();
            long t = cinfo[0], x = cinfo[1];

            if (t > V[(int) x]) continue;

            for (int[] einfo : G.get((int) x)) {
                int nx = einfo[0];
                long cost = einfo[1];
                long nt = t + cost;

                if (heights[(int) x] < heights[nx] && nt < V[nx]) {
                    V[nx] = nt;
                    heap.add(new long[]{nt, nx});
                }
            }
        }
        return V;
    }
}

• 제네릭이라서 이중 List 구현 시, static에서 선언 해놓고 내부 리스트 생성하면서 각 인덱스에 리스트를 한 번 더 초기화한다.
• 파이썬을 풀 땐 오버플로우 생각을 안해서 몰랐는데, 간선 사이즈도 보면서 자료형까지 생각하는 것 잊지 않기.
• for문에서 iterable한 것들 꺼낼 때 한 번에 꺼내지를 못해서 중간 변수들을 지정해줘야하는데, 이런 것들 다 생각해서 변수명 최적화하기.

---

코멘트

*