[백준] 14595번 동방 프로젝트 (Large) (C++)

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

 

 

이 문제는 N개의 방이 일렬로 나열되어 있을때 M개의 방의 관계가 주어지면

그 방은 하나의 방으로 간주할때 남은 방의 개수를 구하는 문제이다.

 

문제만 보면 굉장히 쉽게 유니온 파인드 알고리즘을 사용하여 M만큼 반복하여 마지막에 개수를 판별하면 되지 않을까 생각해서 구현을 했지만

 

시간초과를 받은 문제였다.

 

따라서 이미 합쳤던 방은 다시 반복하지 않은 방식을 사용하여 방을 바꿨던 곳의 최댓값을 갱신하여 반복하는 식으로 하였다.

 

 

M의 배열을 입력받고 이 배열을 정렬시켜 유니온파인드를 사용하여 반복하였다.

 

이때 정렬한 이유는 시작값을 오름차순으로 정렬하기 위해 정렬하였고

 

이후 lo라는 변수를 사용하여 최댓값을 갱신하여 반복하였다.

 

정답코드

 

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"

const int INF = 1e9;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N, M;
int unf[1000001];
vector<pii> v;

int Find(int a) {
    if(a == unf[a]) return a;
    return unf[a] = Find(unf[a]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a > b) unf[a] = b;
    else unf[b] = a;
}

bool isUnion(int a, int b) {
    a = Find(a);
    b = Find(b);

    if(a == b) return true;
    else return false;
}

void Init() {
    for(int i = 1; i <= N; i++) {
        unf[i] = i;
    }
}

void solve() {
    sort(v.begin(), v.end());

    int lo = 0;

    for(auto it : v) {
        int left = it.first;
        int right = it.second;

        lo = max(lo, left);

        for(int i = lo; i <= right; i++) {
            if(!isUnion(lo, i)) {
                Union(lo, i);
            }
        }

        lo = max(lo, right);
    }

    set<int> st;

    for(int i = 1; i <= N; i++) {
        st.insert(Find(i));
    }

    cout << st.size();
}

void input() {
    cin >> N >> M;

    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b});
    }

    Init();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}