BOJ 18085 - Firetrucks Are Red 링크
(2024.03.13 기준 G3)

문제

$n$명의 사람 각각 $m_i$개의 관련된 숫자가 주어진다. 모든 사람들이 직간접적으로 관련된 숫자로 연결되어 있는지 판별 및 연결되어 있다면 $n-1$개의 연결된 두 사람과 숫자를 출력

알고리즘

트리의 성질을 이용 및 DFS로 간선 저장

풀이

모든 사람들이 직간접적으로 연결되어 있고, $n-1$개의 연결된 두 사람과 숫자(이하 간선)으로 표현된다면 이는 즉 트리 형태의 그래프라고 할 수 있다.

일단 각 사람마다 관련된 숫자가 주어지는데, 우리는 이를 두 개의 그래프로 나타내야 한다.
첫 번째는 사람->숫자 그래프인데 이는 평범하게 인접 리스트로 나타내면 된다.
두 번째는 숫자->사람 그래프인데 이는 해시 맵을 이용해서 나타내야 한다. 주어지는 숫자의 범위가 최대 $10^9$이기 때문에 인접 리스트로 나타내면 MLE가 뜰 것이다.

그래프 세팅이 끝났다면 이제 한 정점에서 시작해 DFS를 이용해서 순회를 해봐야 한다. 모든 정점을 방문할 수 있는지 판별해야 하기 때문이다. 그런데 여기서 평범한 DFS라면 정점->정점 방식으로 진행된다. 하지만 이 문제에선 사람에서 숫자, 숫자에서 사람으로 과정을 거쳐야 한다.

편의상 사람을 주 정점, 숫자를 보조 정점이라 생각해보자. 우리가 원하는 것은 주 정점으로 이루어진 그래프에서 모든 정점을 방문하느냐이다. 결국 현재 탐색 중인 주 정점에서 연결된 보조 정점 중 방문하지 않은 보조 정점을 찾아 그 보조 정점과 연결된 주 정점 중 방문하지 않은 주 정점을 찾아 DFS를 진행하면 된다.

간단하게 순서로 설명하면
1. 현재 탐색 중인 주 정점 $i$와 연결된 보조 정점 중 방문하지 않은 보조 정점 $d$를 찾는다.
2. $d$와 연결된 주 정점 중 방문하지 않은 주 정점 $j$를 찾는다.
3. $i \rightarrow d \rightarrow j$를 간선에 저장
4. 1번으로 돌아가 $j$로 다시 시작

이와 같은 과정을 거치면 저장된 간선의 개수는 $n-1$개 또는 그 이하가 된다. DFS로 그래프를 순회하면 사이클이 생기지 않기 때문이다. 그러므로 저장된 간선이 $n-1$개라면 저장된 간선을 출력, $n-1$개 이하라면 impossible를 출력하면 된다.

코드

• C++

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

const int MAXN = 200'000;

struct Edge{
    int i, j, d;
};

vector<int> G[MAXN]; // 사람 -> 숫자
bool v1[MAXN];
map<int, vector<int>> D; // 숫자 -> 사람
map<int, bool> v2;
vector<Edge> edges;

void dfs(int i){
    v1[i] = true;
    for (int d: G[i]){
        if (v2[d]) continue; // 한번 거친 숫자 또한 더 이상 볼 필요 없다.
        v2[d] = true;
        for (int j: D[d]){
            if (v1[j]) continue;
            edges.push_back({i + 1, j + 1, d});
            dfs(j);
        }
    }
}

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

    int n; cin >> n;

    for (int i = 0, m; i < n; i++){
        cin >> m;
        for (int d; m; m--){
            cin >> d;
            G[i].push_back(d);
            D[d].push_back(i);
        }
    }

    // 사람->숫자->사람 과정을 거치면서 DFS를 통해 최대한 많이 방문하면서
    // 지나가는 간선들 저장
    dfs(0);

    // 모든 정점을 방문하였으면 저장한 간선이 트리 형태의 간선이다. 그럼 개수는 n-1개가 된다.
    if (edges.size() != n - 1) cout << "impossible";
    else for (auto [i, j, d]: edges) cout << i << ' ' << j << ' ' << d << '\n';
}

• Python

import sys; input = sys.stdin.readline
sys.setrecursionlimit(222222)
from collections import defaultdict

def dfs(i):
    v1[i] = True
    for d in G[i]:
        if v2[d]:
            continue
        v2[d] = True
        for j in D[d]:
            if v1[j]:
                continue
            edges.append((i + 1, j + 1, d))
            dfs(j)

n = int(input())

G = [[] for _ in range(n)] # 사람 -> 숫자
D = defaultdict(list) # 숫자 -> 사람
for i in range(n):
    m, *d = map(int, input().split())
    for di in d:
        G[i].append(di)
        D[di].append(i)

# 사람->숫자->사람 과정을 거치면서 DFS를 통해 최대한 많이 방문하면서
# 지나가는 간선들 저장
v1 = [False] * n
v2 = defaultdict(bool)
edges = []
dfs(0)

# 모든 정점을 방문하였으면 저장한 간선이 트리 형태의 간선이다. 그럼 개수는 n-1개가 된다.
if len(edges) != n - 1:
    print('impossible')
else:
    for i, j, d in edges:
        print(i, j, d)