[자바] 백준 10979 - 가넷이나 버는게 낫지 않아요?

문제 : boj10979

 

 

  이하의 질문글을 보고 궁금해서 풀어보려다가 물렸다...

 

  결국 31회의 시도로 개인 최장 시도횟수를 찍었고, 결국 뚫긴 했다. 10시간 넘게 걸렸다. 다른 분들 시도횟수까지 포함하면 자바 제출 시도 60회 만에 첫 통과이다 ㅋㅋㅋ

 

1. 자바로 풀 때 이 문제를 위한 메모리 최적화

  일단 이게 자바로는 Scanner는 애초에 느려서 못쓰고, 많이들 사용하는 BufferdReader로 입력받는 순간 메모리 초과가 뜬다. 이게 BufferdReader가 미리 버퍼를 두고 더 많은 양을 미리 입력받아두기 때문에 그렇다. 일반적으로는 그정도론 문제가 없는데 이 문제는 메모리 제한이 너무 낮아 일단 그것만으로도 메모리 초과가 되는 것이다. BufferedReader 생성자 중 두 번째 parameter에 sz를 넣어 버퍼 사이즈를 제한할 수 있으므로 그렇게 버퍼 사이즈를 제한해서 받아야 한다.

  

  이것만으론 충분하지가 않은데, 자바의 경우 c의 free처럼 메모리 잡아둔걸 직접 제거할 방법이 없다. 이걸 gc(garbage collector)가 돌면서 제거하게 되는데, 역시 일반적으론 신경쓰지 않아도 되는데 이 문제는 다른 테스트 케이스의 입력을 미리 받았다고 메모리가 초과될 정도인 문제라, 중간중간 수동으로 gc도 돌려줘야 한다(실제로 안돌리면 통과가 안된다). 또 로직 자체도 최대한 최적화 해야한다. 대충 long으로 처리하면 안되고 int로 되는 부분은 int로 해야 하고, 코드의 V에 해당하는 priority queue(이하 pq)도 배열로 직접 처리하려니 초과나서 pq로 변경했는데, 심지어 pq도 사이즈를 제한해줘야 한다 ㅋㅋ(생성자에 initial size 지정할 수 있다).

 

2. 풀이  

  일단 이 문제를 풀려면 기본적으로 'boj1854 - K번째 최단경로 찾기'(링크) 문제를 풀 수 있어야 한다. 그러니 저것부터 풀고 도전하는걸 추천한다. 왜냐면 1854문제랑 동일한 풀이법인데, 저것보다 메모리 제한이 50%이다. 근데 실제론 이 문제가 메모리를 더 많이 쓴다. 그러니 완벽히 이 문제가 상위호환이므로 저것부터 푸는게 맞다.

 

  그래서 풀이는 저 글 풀이(링크)로 대신한다. 주의할점은 가중치가 2가지란 점인데, t는 작을수록 좋고 g는 높을수록 좋다. 그 부분만 주의하면 위 링크 풀이에서 k=2일 때와 동일하다.

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    class Node implements Comparable<Node> {    // min heap
        int num;
        long t, g;
        public Node(int num, long t, long g) {
            this.num = num;
            this.t = t;
            this.g = g;
        }
        @Override
        public int compareTo(Node o) {
            if (this.t == o.t) {
                return o.g==this.g?0 : (o.g<this.g ? -1 : 1);
            }
            return this.t==o.t?0 : (this.t<o.t ? -1 : 1);
        }
    }

    class V implements Comparable<V> {  // max heap
        long t, g;
        public V(long t, long g) {
            this.t = t;
            this.g = g;
        }
        public boolean chk(long t, long g) {
            if (this.t > t || this.t == t && this.g < g) return true;
            return false;
        }
        public boolean chk(Node node) {
            if (this.t > node.t || this.t == node.t && this.g <= node.g) return true;
            return false;
        }
        @Override
        public int compareTo(V o) {
            if (this.t == o.t) {
                return o.g==this.g?0 : (o.g<this.g ? -1 : 1);
            }
            return this.t==o.t?0 : (this.t>o.t ? -1 : 1);
        }
    }

    private String getAnswer(int tc, int n, ArrayList<int[]>[] edges) {
        PriorityQueue<V>[] v = new PriorityQueue[n+1];
        for (int i = 1; i <= n; i++) v[i] = new PriorityQueue<>(2);

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0, 0));
        v[1].add(new V(0, 0));

        while (!pq.isEmpty()) {
            Node cur = pq.poll();
            if (v[cur.num].size() == 2 && !v[cur.num].peek().chk(cur)) continue;
            ArrayList<int[]> edge = edges[cur.num];
            for (int i = 0; i < edge.size(); i++) {
                int[] tmp = edge.get(i);
                int next = tmp[0];
                long nextT = cur.t+tmp[1];
                long nextG = cur.g+tmp[2];
                if (v[next].size() < 2) {
                    v[next].add(new V(nextT, nextG));
                    pq.add(new Node(next, nextT, nextG));
                    continue;
                }
                if (v[next].peek().chk(nextT, nextG)) {
                    v[next].poll();
                    v[next].add(new V(nextT, nextG));
                    pq.add(new Node(next, nextT, nextG));
                    continue;
                }
            }
        }
        return String.format("Game #%d: Suckzoo ends game in time %d, earning %d garnet(s).\n", tc, v[n].peek().t, v[n].peek().g);
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            ArrayList<int[]>[] edges = new ArrayList[n+1];
            for (int i = 1; i <= n ; i++) edges[i] = new ArrayList<>();
            while (m-->0) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                int t = Integer.parseInt(st.nextToken());
                int g = Integer.parseInt(st.nextToken());
                edges[x].add(new int[]{y,t,g});
                edges[y].add(new int[]{x,t,g});
            }
            String answer = getAnswer(tc, n, edges);
            sb.append(answer);
            System.gc();
        }
        System.out.print(sb);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

ps. 물론 BufferedWriter로 매번 flush 하는것도 해봤었다. 테스트케이스 자체는 몇 개 안되는지 별 차이 없었다.