[자바] 백준 8244 - Tales of seafaring (boj java)

문제 : boj8244

 

  자바로는 정신건강상 시도 안하는걸 추천한다. 자바론 사실상 통과 불가능한 메모리 제한이라 메모리 초과를 뚫기 위해 이상한 짓들을 많이 해야 한다.

 

1. 키 아이디어

  기본 아이디어는 어찌보면 생각하기 어렵고 어찌보면 간단한데 다음의 그래프를 보자. 이 때 k개로 주어진 각각의 'tales that Bytensson has heard'중 하나를 Q라고 칭하겠다.

  이 때 1에서 출발해서 2로 가는 최단길이는 1이다. 그럼 Q가 '1 2 1'이라면 당연히 가능하다. 그럼 '1 2 3'이나 '1 2 5'라도 가능할까? 이것도 가능하다. 왜냐면 한 번 들렸던 곳을 다시 못간다는 제한이 없으므로 다음과 같이 왔다갔다 하면 되기 때문이다. 최단거리는 1이지만, 그 이후로 1+2*n (n은 0부터 무한대)은 모두 가능한 tale이 된다.

  그럼 위에서 '1 2 4'는 가능할까? 위에서 분명 최단길이는 1이라서 이후 1+2*n 이 가능하다고 햇었다. 4는 1+2*n으로 만들 수 없다. 근데 위의 경우 '1 2 4'는 TAK가 된다. 왜냐하면 다음과 같이 사이클을 한번 돌면 4가 되기 때문이다.

   즉, 이 문제에서 중요한 아이디어이자 중요한 데이터는 a에서 출발해 b로 갈 수 있는 홀수최단거리와 짝수최단거리 데이터 이다. 위에서 1에서 2로 가는 홀수최단거리는 1, 짝수최단거리는 4 이다. 이걸 알고 있으면 이제 Q가 '1 2 d'일 때 d가 1+2*n이거나(n은 0부터 무한대), 4+2*n 이면 가능한 tale이 되는 것이다.

 

  이번엔 다음 그래프를 보자.

  Q가 '1 1 2'라면 가능할까? 가능하다. 1에서 뻗어나가는 간선이 하나이상 존재하므로 해당 간선을 왔다갔다 하면 된다. 1->2->1 하면 2번이 가능하니깐('1 1 4', '1 1 1000000000'도 당연히 가능). 그럼 '5 5 2'는 어떨까? 뻗어나가는 간선이 없으므로 불가함을 알 수 있다. 다만 '5 5 0'이나 '1 1 0'은 당연히 가능하다. 출발지에서 안움직여도 되니깐. 그리고 마찬가지로 '1 1 3', '1 1 5', '1 1 99999'도 가능하다(1->2->3->1로 최단 홀수간선이 3임).

 

 

2. 키 아이디어를 적용시킬 방법

2.1 온라인 쿼리 (자바는 불가)

  그럼 이제 위의 아이디어를 적용해 풀기만 하면 된다! 간선간의 가중치가 없으므로, bfs를 사용하면 홀수와 짝수 최단거리를 구할 수 있다. 다만 여기서 문제가 생기는데, 온라인 쿼리로 하자니 dist[5001][5001][2] 크기의 배열이 필요하다(dist[a][b][c]는 a에서 b로가는 홀수최단거리(c=1)와 짝수최단거리(c=0)를 의미한다.). 이걸 int형으로 만들면 메모리초과가 된다. 이 때 간선이 최대 5000개이므로 거리는 5000보다는 어쨌든 낮을 것임을 알 수 있으므로 short로 만들면 메모리초과는 피할 수 있다. 따라서 전처리를 통해 모든 정점에서 정점으로의 최단 홀수, 짝수 거리를 구해두고 k개의 Q를 받으면서 바로바로 '1'의 아이디어를 사용해 TAK와 NIE를 출력해주면 된다.

 

  하지만 위 방법으로는 자바로는 통과가 불가하다. 저 dist를 int던 short던 만드는순간 메모리 초과된다 ㅋㅋㅋ

 

2.2 오프라인 쿼리

  그럼 오프라인 쿼리로 진행을 해야 한다. k개의 Q를 입력받은 후 각 Q의 's t d'중 's'를 기준으로 정렬한다. 이후 s가 바뀔 때 마다 dist[5001][2]의 배열을 만들고 bfs를 진행한 후 정렬된 동일한 s들에 대해 답을 출력하면 된다. 배열 크기가 엄청나게 줄어들어서 메모리를 대폭 줄일 수 있다. 물론 이 경우 Q의 순서가 입력과 달라지므로 별도로 기존 순서를 저장해두어야 한다.

 

 

3. 자바로 통과하기

  2.1로도 C++등 다른 언어론 통과가 가능하다(푼 후 다른분들 코드 확인함). 자바로는 dp[5001][5001][2]대신 dp[5001][2]라는 엄청나게 메모리를 줄이는 2.2 방법을 썼음에도 사실 이대로는 통과가 불가하다 ㅋㅋㅋ. 물론 징징이긴하다. 꼬우면 딴언어 써야지! 맞긴한데 그래도 이런거 뚫는게 또 하나의 재미니깐 ㅠ.

  아무튼 우선 입력도 버퍼를 제한해서 최대한 찔끔찔끔 받아야 하고, gc도 수동으로 돌려줘야 한다. 다만 매번 Q의 s가 변경될 때 마다 돌리면 또 시간초과가 나므로 일정 횟수를 정해두고 gc를 돌려줘야 한다... 그리고 코드의 89~92line처럼 기존에 사용된 연산 중간의 데이터들도 메모리에서 날려주고서야 String으로 된 답을 출력해주는 과정을 진행하면 메모리 초과를 뚫을 수 있다. 메모리 초과때문에 자바로 통과 안되는 문제 최초로 뚫은게 몇 개 되는데, 그 중에서도 이건 역대급으로 뚫기 어려웠다.. 그러니 정신건강상 자바로는 풀지 않는걸 추천한다.

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main extends FastInput {
    class Query implements Comparable<Query> {
        int s, t, d, idx;
        public Query(int s, int t, int d, int idx) {
            this.s = s;
            this.t = t;
            this.d = d;
            this.idx = idx;
        }
        @Override
        public int compareTo(Query o) {
            return this.s-o.s;
        }
    }

    private int[][] findPath(int n, int s, ArrayList<Integer>[] edges) {
        int[][] dist = new int[5001][2];
        for (int i = 1; i <= n; i++) dist[i][0] = dist[i][1] = -1;

        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{s, 0});
        dist[s][0] = 0;
        while (!q.isEmpty()) {
            int[] cur = q.poll();
            ArrayList<Integer> edge = edges[cur[0]];
            for (int i = 0; i < edge.size(); i++) {
                int next = edge.get(i);
                if (dist[next][(cur[1]+1)&1] <= 0) {
                    dist[next][(cur[1] + 1) & 1] = cur[1] + 1;
                    q.add(new int[]{next, cur[1] + 1});
                }
            }
        }
        return dist;
    }

    private void solution() throws Exception {
        int n = nextInt();
        int m = nextInt();
        int k = nextInt();
        ArrayList<Integer>[] edges = new ArrayList[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
        while (m-->0) {
            int a = nextInt();
            int b = nextInt();
            edges[a].add(b);
            edges[b].add(a);
        }
        PriorityQueue<Query> pq = new PriorityQueue<>(k);
        boolean[] answer = new boolean[k];
        for (int i = 0; i < k; i++) {
            int s = nextInt();
            int t = nextInt();
            int d = nextInt();
            pq.add(new Query(s, t, d, i));
        }
        int bfS = -1;
        int[][] dist = null;
        int gcCnt = 0;
        while (!pq.isEmpty()) {
            Query cur = pq.poll();
            if (bfS != cur.s) {
                dist = findPath(n, cur.s, edges);
                bfS = cur.s;
                if (gcCnt++ == 100) {
                    System.gc();
                    gcCnt = 0;
                }
            }
            int s = cur.s; int t = cur.t; int d = cur.d; int idx = cur.idx;
            if (s == t && d == 0) {
                answer[idx] = true;
                continue;
            }
            if (dist[t][d&1] > 0 && d>=dist[t][d&1]) {
                answer[idx] = true;
                continue;
            }
            answer[idx] = false;
        }

        edges = null;
        dist = null;
        pq = null;
        System.gc();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < k; i++) {
            if (answer[i]) sb.append('T').append('A').append('K').append('\n');
            else sb.append('N').append('I').append('E').append('\n');
        }
        System.out.print(sb);
    }

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

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 14;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}