BOJ_1976 C++

HDuckkk·2023년 1월 20일

Beakjoon Online Judge

목록 보기

5/13

BOJ 1976 여행가자

문제
동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.

도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동혁이의 여행 계획에 속한 도시들이 순서대로 주어졌을 때 가능한지 여부를 판별하는 프로그램을 작성하시오. 같은 도시를 여러 번 방문하는 것도 가능하다.

풀이과정

시작하기 앞서 이전에 해결했었던 문제 BOJ_1717과 매우 유사하다.

1717번 문제와 매우 유사하며 가장 중요한 점은 여행의 가능여부를 판단한다는 점이다. 즉, 여행 경로가 한 집합에 포함이 되어있는지를 확인하면 된다. 여기서 나는 다음과 같은 기능을 구현하여 문제풀이를 진행했다.

최고 위치에 부모를 찾는 기능
부모로 구분되어 있는 집합을 합쳐주는 기능

다음과 같이 구현할 수 있다.

최고 위치의 부모를 찾는 함수

int findParent(int num){
    if(num == cities[num]){
        return num;
    }
    else{
        return num = findParent(cities[num]);
    }
}

여기서 확인할 수 있는 점은 재귀함수를 이용했다는 것이다.

부모로 구분되어 있는 집합을 합쳐주는 함수

void Union(int a, int b){ // 그냥 도시의 정보만 입력하면 알아서 최고레벨의 부모를 찾아줌...
    if(findParent(a) == findParent(b)){ // 중복확인
        return;
    }
    
    cities[findParent(a)] = findParent(b);
}

위의 두 함수를 적재 적소에 활용하면 상당히 간단히 해결할 수 있는 문제였다.

총 코드

//BOJ 1976
#include <iostream>
#include <string>
using namespace std;

int cities[200];
int path[1000];
void Union(int a, int b);
int findParent(int num);


int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    // 도시의 수 N, 여행계획에 속한 도시의 수 M
    int N, M;
    cin >> N >> M;

    for(int i=0; i<N; i++){
        cities[i] = i;
    }
    
    // 도시의 연결 정보 입력...
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            int x;
            cin >> x;

            if(x == 1){
                Union(i,j);
            }
        }
    }

    // 도시 여행계확에 속한 도시의 수 M...
    int temp;
    bool ans = true;
    for(int i=0; i<M; i++){
        cin >> path[i];

        if(i == 0){
            temp = findParent(path[i] - 1);
        }
        else{
            if(temp != findParent(path[i] - 1)){
                ans = false;
                break;
            }
        }
    }
    
    if(ans){
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }


    return 0;
}

int findParent(int num){
    if(num == cities[num]){
        return num;
    }
    else{
        return num = findParent(cities[num]);
    }
}

void Union(int a, int b){ // 그냥 도시의 정보만 입력하면 알아서 최고레벨의 부모를 찾아줌...
    if(findParent(a) == findParent(b)){ // 중복확인
        return;
    }
    
    cities[findParent(a)] = findParent(b);
}

// 두가지 기능에 집중하자...!
// 최고 레벨의 부모를 찾는 기능..
// 두 집합을 Union(합)하는 기능..