[BOJ][백준 1976] 여행 가자 - C++

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

1976번: 여행 가자

백준 사이트 1976번 문제, 여행 가자 문제다.

본인은 C++로 문제풀이를 진행하였다.

---

0. 문제 읽기

문제 설명, 간단하다.

• 여행 계획이 가능한 경우 "YES"를 출력하고, 불가능한 경우 "NO"를 출력해야 한다.
• 또한, 여행 계획이 가능하려면 여행 경로상의 모든 도시가 서로 연결되어 있어야 한다.

---

1. 문제풀이 아이디어

• 여행 경로상의 모든 도시가 서로 연결되어 있는지 확인하는 것은 유니온 파인드(Union-Find) 알고리즘을 이용하면 간단히 구현할 수 있다.
• 먼저, 입력받은 도시들의 연결 여부를 기반으로 유니온 파인드를 실행하여 모든 도시들을 연결한다.
• 그리고나서, 주어진 여행 계획에 있는 도시들의 루트가 모두 같은지 확인하여 모든 도시들이 서로 연결되어 있는지를 판단한다.

---

2. 코드 핵심 부분

1) Union-Find 자료구조를 구현한 함수,

   

   find 함수는 처음보면 이해가 잘 되지 않을 수도 있다.

   부모 노드를 재귀적으로 자신을 부모로 갖는 노드까지 찾아 올라가고,

   그 노드를 반환한다.

 

   merge 함수는 A노드와 B노드를 통합시켜주는 역할을 한다.

   이 문제에서 각 도시의 연결이 인접배열 형태로 주어지기 때문에,

   연결된 도시의 경우에 merge함수에 넣어 같은 집합으로 통합해주면 된다.

// Union-Find 자료구조에서 노드 now의 루트 노드를 반환하는 함수
int find(int now) {
    if (Parent[now] == now)     // 현재 노드의 부모 노드가 자기 자신이라면, 현재 노드가 루트 노드임
        return now;
    return Parent[now] = find(Parent[now]);     // 부모 노드를 재귀적으로 찾아감 (경로 압축)
}

// Union-Find 자료구조에서 A와 B를 합치는 함수
void merge(int A, int B) {
    int PA = find(A);   // A의 루트 노드를 찾음
    int PB = find(B);   // B의 루트 노드를 찾음

    if (PA == PB)       // A와 B가 이미 같은 집합에 속해있다면, 합치지 않음
        return;

    Parent[PB] = PA;    // B의 루트 노드의 부모 노드를 A의 루트 노드로 설정하여 A와 B를 합침
}

 

2) 위에서 구현한 Union-Find 자료구조 함수를 실제로 활용하는 부분이다.

   merge 함수를 실행시켜 연결 정보대로 도시들을 통합시켜 주고,

   여행 계획의 도시들이 연결되어 있는지 확인하는 과정이다.

 

   그런데 내가 여기서 처음에 실수를 했는데,

   if (find(Plan[i]) != find(Plan[i - 1])) 이 부분을,

   if (Parent[Plan[i]] != Parent[Plan[i - 1]])로 실행하였었다.

   위에서 통합과정을 거쳤기에 Parent에 그 정보가 모두 반영되어 통합되어 있을 것이라 생각했는데,

   아니었다.

   다시 한번 find로 각 도시의 최종 부모를 찾아 올라가서 그 부모를 비교해야

   정확한 답이 도출된다.

// 여행 계획이 가능한지 여부를 판단하는 함수
void solve() {
    // Union-Find 자료구조를 이용하여, 모든 연결 정보를 합침
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (Map[i][j] == 0)
                continue;
            merge(i, j);
        }
    }

    // 여행 계획에 속한 도시들이 모두 같은 집합에 속하는지 확인
    for (int i = 1; i < M; i++) {
        // 여행 계획이 불가능한 경우
        if (find(Plan[i]) != find(Plan[i - 1])) {
            Ans = "NO";
            return;
        }
    }

    // 여행 계획이 가능한 경우
    Ans = "YES";
}

---

3. 전체 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

// 필요 인자들
int N, M;           // 도시의 수와 여행 계획에 속한 도시의 수
int Map[201][201];  // 도시들 간 연결 정보를 저장하는 이차원 배열
int Plan[1000];     // 여행 계획에 속한 도시들을 저장하는 배열
int Parent[201];    // Union-Find 자료구조를 위한 부모 노드를 저장하는 배열
string Ans;         // 여행 계획이 가능한지 여부를 저장하는 문자열

// 값 입력받는 함수
void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> Map[i][j];   // 도시들 간 연결 정보를 입력받음
        }
    }
    for (int i = 0; i < M; i++) {
        cin >> Plan[i];         // 여행 계획에 속한 도시들을 입력받음
    }
    for (int i = 1; i <= N; i++) {
        Parent[i] = i;          // 초기에는 모든 도시의 부모 노드는 자기 자신으로 설정
    }
}

// Union-Find 자료구조에서 노드 now의 루트 노드를 반환하는 함수
int find(int now) {
    if (Parent[now] == now)     // 현재 노드의 부모 노드가 자기 자신이라면, 현재 노드가 루트 노드임
        return now;
    return Parent[now] = find(Parent[now]);     // 부모 노드를 재귀적으로 찾아감 (경로 압축)
}

// Union-Find 자료구조에서 A와 B를 합치는 함수
void merge(int A, int B) {
    int PA = find(A);   // A의 루트 노드를 찾음
    int PB = find(B);   // B의 루트 노드를 찾음

    if (PA == PB)       // A와 B가 이미 같은 집합에 속해있다면, 합치지 않음
        return;

    Parent[PB] = PA;    // B의 루트 노드의 부모 노드를 A의 루트 노드로 설정하여 A와 B를 합침
}

// 여행 계획이 가능한지 여부를 판단하는 함수
void solve() {
    // Union-Find 자료구조를 이용하여, 모든 연결 정보를 합침
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (Map[i][j] == 0)
                continue;
            merge(i, j);
        }
    }

    // 여행 계획에 속한 도시들이 모두 같은 집합에 속하는지 확인
    for (int i = 1; i < M; i++) {
        // 여행 계획이 불가능한 경우
        if (find(Plan[i]) != find(Plan[i - 1])) {
            Ans = "NO";
            return;
        }
    }

    // 여행 계획이 가능한 경우
    Ans = "YES";
}

// 메인함수
int main() {
    // input
    input();

    // solve
    solve();

    // output
    cout << Ans;

    return 0;
}

---

4. 문제 풀이를 마치며..

백준 채점 결과, 위의 이야기대로 한번 틀렸다..

백준에서 내가 처음으로 풀어본 Union-Find 알고리즘 문제이다.

 

사실 이 알고리즘을 학습한건 2월의 SSAFY 수업이었으니 한참지난 이야긴데,

왜 이제서야 처음으로 풀었냐면..

 

이 알고리즘 수업날 졸업식 때문에 교육을 빠졌었다 ㅠㅠ

그래서 복습을 미루고 미루다가 이제야 겨우 공부하게 되었다.

 

삼성 SW 역량테스트 B형을 처음으로 시험보게 되었었는데

그 대비를 하며 미뤄놨던 알고리즘들을 하나씩 공부하는 중이다.

 

그에 따라 나의 백준 문제풀이도 다양해지고,

그만큼 블로그에 포스팅할 알고리즘들도 다양해질 것이라 기대된다.