백준 1976번 여행 가자 (C++)

문제 링크 : https://www.acmicpc.net/problem/1976

1976번: 여행 가자

공통 부모를 찾는 알고리즘이다. 풀이법은 다양하지만 정석대로 Union-Find 알고리즘을 활용했다.

 

문제 풀이는 다음과 같다.

 

1. n과 m을 입력 받고 n의 사이즈만큼 공통 조상 배열을 초기화해준다. 

또한, n*n의 사이즈만큼 2차원 벡터를 선언한다. 나는 편의상 1부터 계산하기 위해 (n*1)*(n*1)로 선언했다.

    cin >> n >> m;
    uni.resize(n + 1);
    for (int i = 1; i <= n; i++) uni[i] = i; // 공통조상의 합집합을 만들 배열
    vector<vector<int>> v(n + 1, vector<int>(n + 1, 0)); // (n*1) * (n*1) 배열 
    vector<int> des(m + 1); // 최종적으로 서로 이어지는 여행지인지 판별하기 위한 m 사이즈 배열
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cin >> v[i][j];
    }

 

2. 도시의 연결 정보에서 값이 1이고 (v[i][j] = 1) 서로 합집합의 여부를 판단하지 않았을 경우(uni[i]!=uni[j]), Union-Find 알고리즘을 실행한다.

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (v[i][j] == 1 && uni[i] != uni[j]) Union(i, j);
        }
    }

 

3. 다음은 Union - Find 알고리즘이다. 아래 코드를 대략적으로 훑고 세세한 설명을 이해해보자.

int Find(int v) {
    if (v == uni[v]) return v; // 2
    uni[v] = Find(uni[v]); // 3
    return uni[v];
}

void Union(int a, int b) {
    a = Find(a); // 1
    b = Find(b); // 1
    if (a < b) uni[b] = a; // 4
    else uni[a] = b; // 5
}

(1) 매개 변수로 받았던 i와 j를 Union 알고리즘으로 공통 조상의 합집합을 가려낸다.

(2) 만약 v[i] = i일 경우, 아직 공통 조상의 합집합을 가려내지 않았거나 혹은 해당 배열의 값이 공통 조상이라는 것을 뜻한다. 이 경우에는 해당 값을 return해주면 된다.

(3) 그렇지 않을 경우, 다시 Find 알고리즘을 통해 공통 조상을 찾아내 값을 갱신해준 뒤 return 한다. 

(4) 다시 Union 알고리즘으로 돌아와 합집합을 진행해준다. 합집합의 뜻은, 최초에 매개변수로 받았던 i와 j를 통해 v[i]와 v[j]의 공통 조상을 합집합으로 묶어주다는 뜻이다.

(5) 이때 유의할 점이, (4)번과 (5)번의 코드를 볼 경우 값이 더 작은 쪽을 공통 조상으로 저장한다는 점이다.

 

4. 다시 main함수로 복귀해서 타겟 여행지의 공통조상이 같을 경우 YES를, 그렇지 않을 경우 NO를 출력한다.

    temp = uni[des[1]];
    for (int i = 2; i <= m; i++) {
        if (temp == uni[des[i]]) {
            if (i == m) ch = true;
        }
        else {
            ch = false;
            break;
        }
    }
    if (!ch) cout << "NO" << "\n";
    else cout << "YES" << "\n";

 

#include <iostream>
#include <algorithm>
using namespace std;

vector<int> uni;

int Find(int v) {
    if (v == uni[v]) return v;
    uni[v] = Find(uni[v]);
    return uni[v];
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a < b) uni[b] = a;
    else uni[a] = b;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, m, temp;
    bool ch = false;
    cin >> n >> m;
    uni.resize(n + 1);
    for (int i = 1; i <= n; i++) uni[i] = i;
    vector<vector<int>> v(n + 1, vector<int>(n + 1, 0));
    vector<int> des(m + 1);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cin >> v[i][j];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (v[i][j] == 1 && uni[i] != uni[j]) Union(i, j);
        }
    }
    for (int i = 1; i <= m; i++) cin >> des[i];
    temp = uni[des[1]];
    for (int i = 2; i <= m; i++) {
        if (temp == uni[des[i]]) {
            if (i == m) ch = true;
        }
        else {
            ch = false;
            break;
        }
    }
    if (!ch) cout << "NO" << "\n";
    else cout << "YES" << "\n";
    return 0;
}