BOJ 1976 - 여행 가자 링크
(2023.04.05 기준 G4)

문제

N개의 도시가 주어지고 임의의 두 도시 사이에 길이 있는지 주어진다.
M개의 여행 계획에 속한 도시가 주어지고, 같은 도시를 여러 번 방문이 가능하다면, 주어진 여행 계획이 가능한 여행 계획인지 판별.

알고리즘

여러 번 방문이 가능하니, 연결만 되어 있으면 된다. 그러므로 분리 집합.

풀이

만약 여러 번 방문이 불가능하다면 아마 DFS로 풀어야 할 것이다. 하지만, 여러 번 방문이 가능하니 그냥 여행 계획에 속해 있는 모든 도시가 연결만 되어 있다면 전부 방문할 수 있게 된다.

연결되어 있는 도시끼리 union을 하고, 여행 계획에 속해 있는 도시 중 하나라도 같은 집합에 속해 있지 않다면 불가능한 것이 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

vector<int> parent(200);

int find(int u){
    if (parent[u] != u) parent[u] = find(parent[u]);
    return parent[u];
}

void merge(int u, int v){
    u = find(u);
    v = find(v);
    if (u < v) parent[v] = u;
    else parent[u] = v;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, M;
    cin >> N >> M;

    int matrix[N][N];
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> matrix[i][j];

    iota(parent.begin(), parent.begin() + N, 0);
    // i번 도시와 j번 도시가 연결되어 있다면 union
    for (int i = 0; i < N - 1; i++) for (int j = i + 1; j < N; j++) if (matrix[i][j]) merge(i, j);

    int plan[M];
    for (int i = 0; i < M; i++) cin >> plan[i];
    // 계획에 속한 도시들이 하나라도 같은 집합에 있지 않다면 불가능한 여행 계획
    for (int i = 0; i < M - 1; i++) if (find(plan[i] - 1) != find(plan[i + 1] - 1)){
        cout << "NO";
        return 0;
    }
    cout << "YES";
}

• Python

import sys; input = sys.stdin.readline

def find(u):
    if parent[u] != u:
        parent[u] = find(parent[u])
    return parent[u]

def union(u, v):
    u = find(u)
    v = find(v)
    if u < v:
        parent[v] = u
    else:
        parent[u] = v

N = int(input())
M = int(input())
matrix = [list(map(int, input().split())) for _ in range(N)]

parent = [i for i in range(N)]
for i in range(N - 1):
    for j in range(i + 1, N):
        if matrix[i][j]: # i번 도시와 j번 도시가 연결되어 있다면 union
            union(i, j)

plan = list(map(int, input().split()))
for i in range(M - 1): # 계획에 속한 도시들이 하나라도 같은 집합에 있지 않다면 불가능한 여행 계획
    if find(plan[i] - 1) != find(plan[i + 1] - 1):
        print('NO')
        break
else:
    print('YES')