여행가자.md

DONE_DATE	2025/01/09

여행 가자

난이도

• 골드 4

문제

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

알고리즘 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 분리 집합
• 유니온 파인드 ?

정답코드

#include <bits/stdc++.h>

using namespace std;

class UnionFind {
private:
    vector<int> parent;
    vector<int> rank;
public:
    UnionFind(int n) {
        parent.resize(n); 
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i; 
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 경로 압축
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    // 두 원소가 같은 집합에 속해 있는지 확인
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

int main() {
    int N;
    cin >> N;
    UnionFind uf(N + 1);

    int M;
    cin >> M;

    bool connected;
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            cin >> connected;
            if (connected) {
                uf.unite(i, j);
            }
        }
    }

    int city;
    cin >> city;
    for (int i = 0; i < M - 1; ++i) {
        int nextCity;
        cin >> nextCity;
        if (uf.connected(city, nextCity)) {
            city = nextCity;
        } else {
            cout << "NO";
            return 0;
        }
    }

    cout << "YES";

    return 0;
}

회고

• 입력으로 주어지는 도시들이 모두 연결되어 있는지 여부를 판단하는 문제이다.
• 유니온 파인드를 사용하여 각 도시들이 연결되어 있는지 판단하였다.

유니온 파인드란

• 유니온 파인드는 먼저 각 배열에 자기 자신을 부모로 설정한다.
• find 함수를 보면 경로 압축을 하고 있다. 이는 find 함수를 호출할 때마다 부모를 찾아가는데 이를 경로 압축을 통해 부모를 바로 찾을 수 있도록 한다.
• 즉 같은 집합인지 비교하는 기준은 공통된 부모를 가지고 있느냐이다.
• 또 rank를 통해 두 집합의 높이를 비교하여 더 낮은 높이의 집합을 더 높은 높이의 집합에 붙이는 방식으로 집합을 합친다.
• 왜 rank 비교를 해야하나면 그래야 높이를 최소화하여 find 함수의 시간복잡도를 줄일 수 있기 때문이다.
• 유니온 파인드는 크루스칼에도 사용되는 걸로 알고 있다.
• 잘 숙지해두자./