백준 20156 자바 - 기왕 이렇게 된 거 암기왕이 되어라 (BOJ 20156 JAVA)

문제 : boj20156

 

 

  구현도 빡쌘편이고 함정카드도 꽤 생각하기 힘든 녀석이었다. 역시 항상 20퍼대 이하의 정답률 문제들은 항상 뭔가가 있다. 그리고 요즘 스트릭만 채운다고 실버위주로 풀다가 오랜만에 플래 풀어보니 체감이 확 된다 ㅋㅋㅋ 

 

 

1. 우선 다른거 다 빼고 동일 스터디 그룹인지 어떻게 알 수 있을지 생각해보자.

  이 부분은 간단하다. union-find를 사용해 disjoint set을 파악하면 된다. 입력으로 받은 B와 C가 동일한 그룹인지 확인하려면, B와 C가 같은 그룹내에 속한지 판단만 하면 알 수 있다(일반적으로 union-find를 사용했다면 결국 find(B) == find(C) 라면 동일 그룹이다).

 

 

2. 그룹이 해제는 어떻게 해요? 생각할게 너무 많아요!

  그룹을 해제하는건 어렵지만, 그룹을 연결하는건 쉽다. 그렇다면 그룹을 해제하는 대신 그룹을 연결하는 것으로 변경할 수 없을까? 이 문제는 라운드마다 그룹이 중간중간 연결되었다가 해제되는 문제도 아니고, 그냥 매번 해제만 되는 문제이므로 사실 라운드를 거꾸로 돌려버리면 그룹을 연결하는 형태가 된다. 따라서 오프라인 쿼리 개념을 적용해서 생각해 볼 수 있다.

(오프라인 쿼리 : 쿼리 순서를 변경해도 문제없이 풀 수 있는 경우, 쿼리 순서를 마음대로 변경해서 푸는걸 뜻함. '2'에선 좀 개념을 이해하기 힘들 수 있지만 '3'에서 더 확실히 알 수 있음)

 

  라운드 3에서 1번과 그 학생의 멘토가 해제된다고 해보자. 그럼 라운드 3 이전에서 이후로 넘어가는건 그룹 해제이지만, 라운드 3 이후에서 이전으로 거꾸로는 그룹 연결이 된다. 따라서 라운드를 1번부터 보지 말고 M번부터 거꾸로 0번(0번은 초기상태로, 해제 된 그룹이 없는 상태)까지 내려오면 된다.

 

  어떻게 그렇게 할 수 있냐면, 라운드 정보 M개를 일단 입력받으면서 해제될 정점에 대한 정보를 HashSet 등에 넣어둔다. 그리고 N개의 멘토 정보에 대해 직전에 있던 라운드 정보 M개에 없던 정점에 대해서만 그룹을 미리 맺어둔다. 그리고 라운드 M부터 0까지 거꾸로 진행하면, 그룹 해제 연산이 필요가 없어진다.

 

 

3. 그럼 쿼리는 어떻게 처리하나요? 모든 라운드에 대한 union-find 정보를 저장해두는건가요? 

  '2'의 개념을 실제 쿼리에 적용하려면 거꾸로 라운드를 진행하면서 모든 union-find 결과를 저장해두거나, 혹은 쿼리의 A값이 항상 내림차순이어야 한다. 전자의 경우 못해도 O(N^2)의 메모리 복잡도가 들어가므로, 메모리 초과를 피하기 힘들다. 따라서 라운드 뿐 아니라 쿼리에도 오프라인 쿼리 개념을 넣어보자.

 

  이 문제의 쿼리는 쿼리 자체가 다른 쿼리에 영향을 끼치지 않으므로 순서를 변경하더라도, 원래 입력으로 들어온 순서만 별도로 기억하고 있다면 답을 출력하는데 문제가 없다. 따라서 K개의 쿼리들을 A를 기준으로 내림차순으로 정렬한 후(단, 입력으로 들어온 순서는 기억을 별도로 해야 한다.) 라운드를 거꾸로 진행하면서 그룹을 맺으며 답을 출력해주면 된다.

 

 

4. 예시!

  다음과 같은 입력을 보자.

6 3 4
2 3 4 5 6 -1
1
3
5
0 1 6
2 2 6
2 3 6
3 1 6

 

4.1 처음에 전부 연결한다면 다음과 같을 것이다. 하지만 이렇게 되면 라운드를 진행하면서 그룹을 해제해야한다.

 

4.2 따라서 미리 M개의 입력에 대해 파악한 후(1,3,5), 미리 끊어놓는다. 즉 M개의 입력에 있었던 항목에 대해서는 제외하고 나머지만 그룹을 연결한다. 

 

4.3 그리고 라운드를 역순으로 진행하기 위해 쿼리를 A값을 기준으로 역순으로 정렬한다. 이 때 입력 순서는 정답 출력을 위해 알고 있어야 한다. A만 동일하다면 B,C 값의 순서는 어떻게 되어도 상관없다.

 

4.4 이제 정렬해둔 순서대로 하나씩 진행해보자. 우선 '3 1 6'의 입력에 대해 A=3은 마지막 라운드인 3라운드가 진행된 이후이므로, 끊어질게 모두 끊어진 상태가 된다. 그러니 '4.2' 상태 그대로 확인하면 된다. 현재 1과 6은 서로 다른 스터디 그룹이므로 'No'가 답이 된다. 이 때 기록해둔 입력 순서를 기준으로 해당 순서에 맞는 정답 순서에 정답을 출력해주면 된다.

 

4.5 다음으로 '2 2 6'을 보자. 이 때 A값이 감소하였으므로, 그에 맞춰 '3라운드'에 진행됬던 멘토 끊기(?)를 반대로 연결해줘야 한다. 

 

4.6 마지막으로 '0 1 6'을 보자. 이 때 A값은 2단계가 감소했다. 상관없다. 라운드 역순으로 내려오면서, 현재 보고 있는 쿼리의 A값까지 멘토를 연결해주면서 내려오면 된다. 이 경우 끊겼을 모든 그룹이 이어진 '4.1'의 상태가 된다.

4.7 그럼 이제 원래 입력으로 들어왔던 순서대로 정답을 알 수 있다! 그러니 '정답 순서'대로 출력해주기만 하면 통과할 수 있..다?

 

 

 

 

 

 

 

 

 

------ 함정카드 스포 주의. 직접 풀면서 느껴보려면 아래로 내리지 말 것. ------

 

 

 

 

 

 

 

5. 하지만 이 문제의 정답률은 20%대. 만만치 않은 녀석이다.

  그렇다. 함정카드가 있다. 이 문제에서는 어디에도 이미 M라운드에서 끊어진 스터디 그룹에 대해 이후에 다시 입력으로 들어오지 않는다는 말이 적혀있지 않다. 그래도 악독(?)하진 않은 것이, '만약 멘토가 없다면 아무것도 하지 않는다.' 라고 힌트를 이미 줬다. 눈치채지 못했을 뿐.

 

  그러니 만약 입력이 다음과 같다면 (M개가 전부 동일함) 1라운드에서만 끊어져야 하고, 이후 2, 3 라운드에서는 아무일도 하지 않아야 한다.

6 3 4
2 3 4 5 6 -1
3
3
3
0 1 6
2 2 6
2 3 6
3 1 6

 

  하지만 '4'에서 제시한 방법대로 한다면 3라운드에서 이미 '3'을 연결해버릴 것이다. 그래서 실제론 답이

Same Same;
No;
No;
No;

이지만, '4'에서 제시한 방법 그대로 짠다면

Same Same;
Same Same;
Same Same;
No;

이 되버린다. 

 

  따라서 별도로 1라운드에서만 '3'이 연결되도록 처리해줘야 한다. 내 경우엔 이걸 위해 44 line에서 아래와 같이 이미 나왔던 번호라면 0으로 변경하도록 처리했다. (그리고 0번의 멘토는 -1로 무시되도록 해뒀다.)

if (chk.contains(round[i])) round[i] = 0;

 

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.Arrays;
import java.util.HashSet;

public class Main extends FastInput {
    private static final String SAME = "Same Same;\n";
    private static final String DIFF = "No;\n";

    private int[] parents;

    private int find(int a) {
        if (parents[a] < 0) return a;
        return parents[a] = find(parents[a]);
    }

    private void union(int a, int b) {
        if (b == -1) return;

        a = find(a);
        b = find(b);
        if (a == b) return;
        int h = parents[a]<=parents[b]?a:b;
        int l = parents[a]<=parents[b]?b:a;
        parents[h]+=parents[l];
        parents[l] = h;
    }

    private void solution() throws Exception {
        int n = nextInt();
        int m = nextInt();
        int k = nextInt();

        parents = new int[n+1];
        Arrays.fill(parents, -1);
        int[] mento = new int[n+1];
        for (int i = 1; i <= n; i++) mento[i] = nextInt();
        mento[0] = -1;

        int[] round = new int[m+1];
        HashSet<Integer> chk = new HashSet<>();
        for (int i = 1; i <= m; i++) {
            round[i] = nextInt();
            if (chk.contains(round[i])) round[i] = 0;
            else chk.add(round[i]);
        }

        for (int i = 1; i <= n; i++) {
            if (!chk.contains(i))
                union(i, mento[i]);
        }
        chk = null;

        Query[] queries = new Query[k];
        for (int i = 0; i < k; i++) queries[i] = new Query(i, nextInt(), nextInt(), nextInt());
        Arrays.sort(queries);

        boolean[] answer = new boolean[k];
        for (int i = 0; i < k; i++) {
            Query cur = queries[i];
            while (m>cur.a) union(round[m], mento[round[m--]]);
            answer[cur.idx] = find(cur.b) == find(cur.c);
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < k; i++) sb.append(answer[i]?SAME:DIFF);
        System.out.print(sb);
    }

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

class Query implements Comparable<Query> {
    int idx, a, b, c;
    public Query(int idx, int a, int b, int c) {
        this.idx=idx; this.a=a; this.b=b; this.c=c;
    }

    @Override
    public int compareTo(Query o) {
        return o.a - this.a;
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    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();
        boolean neg = (c == '-');
        if (neg) c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        if (neg) return -ret;
        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++];
    }
}