4 - 2. Closing the Farm (Gold)

https://www.acmicpc.net/problem/12012

12012번: Closing the Farm (Gold)

 

완전 좋아하는 알고리즘 중 하나인 서로소 집합 문제인데, 거기에 오프라인 쿼리를 잘 곁들인 문제라 소개해볼까 가져왔습니다.

 

 

USACO 우리의 주인공 농부 존

문제는 존이 소와 여행을 떠나기 위해 농장을 폐쇄하는 경우, 각 시점마다 농장의 상태를 답으로 출력하는 문제입니다.

농장의 개수(N): 20만, 농장 사이 길의 개수(M): 20만

 

어떤 한 농장이 폐쇄 됐을때, 아직 개방되어있는 각 농장끼리 연결이 돼 있다면 YES, 그렇지 않으면 NO를 출력합니다.

 

 

문제가 흘러가는 프로세스를 보면, 농장이 서로 연결돼 있다는 것은 서로소 집합으로 처리할 수 있을 거라는 느낌이 확 와닿습니다.

그런데, 전반적인 프로세스는 서로소 집합이 동작하는 것과는 반대로 동작해야할 것 같습니다.

서로소 집합 코드에서 어떤 변경을 통해 구현하는 문제도 꽤 있습니다만, 해당 문제는 쿼리를 역방향으로 돌리고 그 결과를 다시 역으로 출력해주면 됩니다.

 

정확하게 어떻게 진행되는지 예제로 주어진 입력을 그림을 그려보며 이해해봅시다.

그림1. 농장 전체 구조

처음 농장은 이런 모습일겁니다.

여기서 쿼리 순서대로 진행된다면, 아래와 같이 그려질 수 있겠죠.

 

 

그림 2. 쿼리 진행

 이렇게 폐쇄된 농장과 연결된 길도 마찬가지로 차단됩니다. 이 순서를 역으로 가져간다면 어떨까요?

 

일반적인 서로소 집합 처럼 merge를 진행하며, merge된 집합의 크기를 구해줄 수 있겠죠.

그리고 그 크기가 현재까지 등장한 농장의 개수와 같다면 완전히 연결된 상태이고, 그렇지 않다면 분리된 농장이 있다고 판단 가능합니다.

 

그런데, 매번 인접한 농장을 폐쇄하는 것이 아닙니다.

즉, 각 농장이 등장했는지 체크하고 현재 농장에서 merge 가능한 농장을 파악해야한다는 의미죠.

 

위의 예제에서 쿼리를 역으로 진행할 때 4번 농장을 복구시키는 경우가 이와 같습니다.

즉,  3번 농장이 쿼리로 들어왔을때 이어 붙일 수 없습니다. 아무 작업 없이 분리된 집합이라 여기고 그대로 넘기면 다음 3번이 마지막 쿼리로 들어 왔을 때, 전체 농장이 완전히 연결되어야하는데 관련 정보가 없으니 연결할 수 없겠죠.

 

밑줄 친 두가지 경우를 잘 고려해서 코드를 구현해보면 아래와 같습니다.

 

Closing the Farm(Gold) 정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    private static final String FULLY = "YES\n";
    private static final String DISTRIBUTED = "NO\n";

    private static ArrayList<ArrayList<Integer>> farms = new ArrayList<>();
    private static int[] parent;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        parent = new int[N];
        Arrays.fill(parent, -1);

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

        while(M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int node1 = Integer.parseInt(st.nextToken()) - 1;
            int node2 = Integer.parseInt(st.nextToken()) - 1;

            farms.get(node1).add(node2);
            farms.get(node2).add(node1);
        }

        ArrayDeque<Integer> query = new ArrayDeque<>();
        while(N-- > 0) {
            query.push(Integer.parseInt(br.readLine()) - 1);
        }

        System.out.print(travel(query));
    }

    private static String travel(ArrayDeque<Integer> query) {
        long count = 0;
        boolean[] visit = new boolean[query.size()];

        ArrayDeque<String> stack = new ArrayDeque<>();
        while(!query.isEmpty()) {
            int current = query.pop();
            count++;

            visit[current] = true;

            for(int adj: farms.get(current)) {
                if(!visit[adj]) continue;
                merge(current, adj);
            }

            stack.push(count == -parent[find(current)] ? FULLY: DISTRIBUTED);
        }

        StringBuilder sb = new StringBuilder();
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        return sb.toString();
    }

    private static int find(int x) {
        if (parent[x] < 0) return x;
        return parent[x] = find(parent[x]);
    }

    private static void merge(int x, int y) {
        x = find(x);
        y = find(y);

        if(x == y) return;

        if (parent[x] < parent[y]) {
            parent[x] += parent[y];
            parent[y] = x;
        }
        else {
            parent[y] += parent[x];
            parent[x] = y;
        }
    }
}

시간 복잡도는 어떻게 될까요? 겉으로 보긴엔 O(NM * log∂(N)) 같은데, 맞나요?

그렇다면 시간 초과로 코드가 돌지 못했겠죠.

 

 

여기서 아래 코드를 조금 더 분석해봅시다.

while(!query.isEmpty()) {
	int current = query.pop();
	count++;

	visit[current] = true;

	for(int adj: farms.get(current)) {
		if(!visit[adj]) continue;
		merge(current, adj);
	}
            
	stack.push(count == -parent[find(current)] ? FULLY: DISTRIBUTED);
}

이렇게만 보면 반복문이 중첩 돼 있어, O(NM) 즉, 시간 초과가 날 것 같습니다.

N, M이 최대 20만이니까 100억인데 이렇게 겉으로만 보고 시간복잡도를 분석하면 문제를 제대로된 방식으로 접근할 수 없는 경우가 생깁니다.

 

물론 각 농장이 모두 연결될 수 있다면, 도형에서 선분의 개수를 세는 방식이므로 N(N - 1)/2로 계산할 수 있습니다. (마찬가지로 약 100억)

그러나, 이 문제는 선분의 개수 즉, M이 20만으로 제한되어있습니다. 그러니 N이 20만인 경우엔 그래프가 트리와 유사한 모양새를 나타낼 것입니다. (트리 구조에서 간선이 한개 추가된 경우)

또는, 완전 고립된 농장들을 두고 복잡하게 이어져 있을텐데 이 또한 20만 * 20만의 시간복잡도를 유도하지는 못합니다.

 

최악일 것 같은 경우를 예측해보자면 적당한 농장 개수에 최대 20만개의 간선이 적절히 분배된 모양이겠죠.

그렇게 되기 위해선 아마도 sqrt(20만)의 값이 노드의 갯수가 되는 경우일 것 같습니다. (간단한 계산이니 설명은 생략합니다.)

 

즉, N이 약 400 ~ 500 사이인 경우 20만개 간선 M이 각 노드별로 400 ~ 500개 정도 분배된 경우며, 따라서 제한 시간안에 문제를 해결할 수 있습니다.

 

 

 

 

시간 복잡도: sqrt(20만)의 제곱이므로 20만으로 표현했습니다.

O(20만 * log∂(N))