BOJ 1976 : 여행 가자 [C++]

 

1976번: 여행 가자

 

작년에 푼 문제인데 다시 한번 풀어봤다.

 

도시의 수가 적고, 같은 도시를 방문해도 된다는 부분에서 어떻게든 목적지로 가기만 하면 된다고 생각해

플로이드 워셜로 A도시에서 B도시로 갈 수 있는지를 모두 구해놓으면 된다고 생각했다.

 

코드

#include <iostream>

int N, M;
bool has_road[201][201];
int travel[1001];

int main() {
    std::cin >> N >> M;

    int cell;
    for (int i = 1; i < N + 1; i++) {
        for (int j = 1; j < N + 1; j++) {
            std::cin >> cell;
            if (cell == 1) {
                has_road[i][j] = true;
            }
            if (i == j) {
                has_road[i][j] = true;
            }
        }
    }

    for (int k = 1; k < N + 1; k++) {
        for (int i = 1; i < N + 1; i++) {
            if (i == k) {
                continue;
            }
            for (int j = 1; j < N + 1; j++) {
                if (i == j || j == k) {
                    continue;
                }
                if (has_road[i][j] || (has_road[i][k] && has_road[k][j])) {
                    has_road[i][j] = true;
                }
            }
        }
    }

    for (int i = 0; i < M; i++) {
        std::cin >> travel[i];
    }

    for (int i = 1; i < M; i++) {
        if (!has_road[travel[i - 1]][travel[i]]) {
            std::cout << "NO\n";
            return 0;
        }
    }
    std::cout << "YES\n";

    return 0;
}

 

 

그런데 문제 분류를 보니 분리 집합(유니온 파인드)이 들어있어서 제출 기록을 보니,

예전에도 플로이드 워셜로 풀어놓고 분리 집합으로 재도전한 기록이 있었다.

 

분리 집합(유니온 파인드) 코드

#include <iostream>

int n, m;
int parents[201];
int plan[1001];

int find_parent(int target) {
    if (target == parents[target]) {
        return target;
    } else {
        return parents[target] = find_parent(parents[target]);
    }
}

int main() {
    std::cin >> n;
    std::cin >> m;
    
    for (int i = 1; i < n + 1; i++) {
        parents[i] = i;
    }
    
    bool input;
    for (int i = 1; i < n + 1; i++) {
        for (int j = 1; j < n + 1; j++) {
            std::cin >> input;
            if (input) {
                int root_i = find_parent(i);
                int root_j = find_parent(j);
                if (root_i < root_j) {
                    parents[root_i] = root_j;
                } else {
                    parents[root_j] = root_i;
                }
            }
        }
    }

    bool possible = true;
    std::cin >> plan[0];
    for (int i = 1; i < m; i++) {
        std::cin >> plan[i];
        if (find_parent(plan[i - 1]) != find_parent(plan[i])) {
            possible = false;
        }
    }

    if (possible) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }

    return 0;
}