[Baekjoon] 10891 – Cactus? Not cactus?

📖 문제 이해하기

선인장(Cactus) 그래프는 그래프 이론에서 특별한 성질을 가진 연결 그래프입니다. 핵심은 각 정점이 최대 하나의 단순 사이클에만 속할 수 있다는 제약입니다. 다시 말해, 어떤 정점도 두 개 이상의 서로 다른 사이클의 일부가 될 수 없습니다.

예를 들어, 정점이 4개이고 간선이 (1,2), (2,3), (3,4), (4,1)인 그래프를 생각해보겠습니다. 이는 하나의 사이클 1→2→3→4→1을 형성하며, 각 정점은 정확히 이 사이클에만 속하므로 선인장입니다. 반면, (1,2), (2,3), (3,1), (2,4), (4,5), (5,2)로 구성된 그래프에서는 정점 2가 두 개의 서로 다른 사이클 1→2→3→1과 2→4→5→2에 동시에 속하므로 선인장이 아닙니다.

이 문제에서 중요한 제약조건은 그래프가 연결되어 있다는 점입니다. 따라서 모든 정점이 하나의 연결 컴포넌트에 속하며, DFS 한 번으로 전체 그래프를 탐색할 수 있습니다.

🧠 첫 번째 시도와 한계점

처음 이 문제를 접했을 때 가장 직관적으로 떠오르는 방법은 모든 사이클을 찾아서 각 정점이 몇 개의 사이클에 속하는지 세는 것입니다. 각 정점에서 시작해서 모든 가능한 경로를 탐색하며 자기 자신으로 돌아오는 경로를 찾고, 발견된 사이클들 간에 공통 정점이 있는지 확인하는 방식입니다.

하지만 이 접근법은 심각한 성능 문제를 안고 있습니다. 일반적인 그래프에서 사이클의 개수는 지수적으로 증가할 수 있으며, N = 100,000인 경우 거의 모든 정점 쌍이 연결된 조밀한 그래프에서는 수백만 개 이상의 사이클이 존재할 수 있습니다. 각 사이클을 개별적으로 찾고 저장하는 작업만으로도 메모리와 시간이 폭발적으로 증가합니다.

더 큰 문제는 사이클 간의 교집합을 확인하는 과정입니다. 모든 사이클 쌍에 대해 공통 정점을 확인해야 하므로 O(사이클 개수²)의 비교 연산이 필요합니다. 이는 현실적으로 불가능한 시간 복잡도를 만들어냅니다.

💡 핵심 아이디어: 정점별 사이클 참여 횟수 계산

문제를 다르게 바라보면 해결책이 보입니다. 각 정점이 몇 개의 사이클에 참여하는지만 알면 되고, 실제 사이클의 구체적인 형태는 알 필요가 없습니다. 선인장의 정의에 따르면 모든 정점이 최대 1개의 사이클에만 속해야 하므로, 2개 이상의 사이클에 속하는 정점이 하나라도 발견되면 즉시 “선인장이 아니다”라고 판단할 수 있습니다.

이 관점에서 핵심 질문은 “DFS 탐색 중에 각 정점이 사이클에 참여하는 횟수를 어떻게 효율적으로 셀 수 있는가?”입니다. DFS는 그래프의 구조적 특성을 파악하는 데 매우 강력한 도구이며, 특히 back edge(역방향 간선)를 통해 사이클의 존재를 감지할 수 있습니다.

DFS 과정에서 현재 정점에서 인접한 정점들을 방문할 때, 각 인접 정점과의 관계는 다음 중 하나입니다: 아직 방문하지 않은 정점(tree edge가 생성됨), 이미 방문 완료된 정점(forward edge 또는 cross edge), 또는 현재 DFS 경로상에 있는 정점(back edge가 생성됨). 이 중에서 back edge는 사이클의 존재를 직접적으로 나타냅니다.

📘 DFS와 Back Edge
DFS(깊이 우선 탐색)에서 back edge는 현재 탐색 경로상의 조상 정점으로 향하는 간선을 의미합니다. Back edge가 발견되면 해당 간선이 새로운 사이클을 형성함을 나타냅니다. DFS의 이런 특성을 활용하면 복잡한 사이클 탐지 알고리즘 없이도 각 정점의 사이클 참여도를 효율적으로 계산할 수 있습니다.

🔍 알고리즘 동작 과정 상세 분석

구체적인 예제를 통해 알고리즘이 어떻게 작동하는지 살펴보겠습니다. 정점 6개와 간선 (1,2), (2,3), (3,4), (4,2), (2,5), (5,6), (6,2)로 구성된 그래프를 고려해보겠습니다.

DFS를 정점 1부터 시작합니다. dfs_num[1] = dfs_low[1] = 1로 설정하고 방문 상태를 1로 표시합니다. 정점 1의 인접 정점은 2뿐이므로 정점 2로 이동합니다.

정점 2에서 dfs_num[2] = dfs_low[2] = 2로 설정합니다. 정점 2의 인접 정점들은 1, 3, 4, 5, 6입니다. 정점 1은 부모이므로 건너뛰고, 정점 3으로 이동합니다.

정점 3에서 dfs_num[3] = dfs_low[3] = 3으로 설정하고, 인접 정점 2는 부모이므로 건너뛰고 정점 4로 이동합니다.

정점 4에서 dfs_num[4] = dfs_low[4] = 4로 설정합니다. 정점 4의 인접 정점들은 3과 2입니다. 정점 3은 부모이므로 건너뛰고, 정점 2를 확인합니다. 정점 2는 현재 방문 중인 상태(vis[2] == 1)이므로 back edge입니다. 이때 dfs_low[4] = min(4, 2) = 2로 업데이트되고, count가 1 증가합니다.

정점 4에서 DFS가 완료되면서 정점 3으로 돌아갑니다. dfs_low[4] <= dfs_num[3] (2 <= 3)이므로 count가 1 증가합니다. 정점 3의 최종 count는 1입니다.

정점 3에서 정점 2로 돌아갑니다. 마찬가지로 dfs_low[3] <= dfs_num[2] (2 <= 2)이므로 count가 1 증가합니다. 이제 정점 2에서 정점 5로 이동합니다.

정점 5와 정점 6 사이에서도 유사한 과정이 반복됩니다. 정점 6에서 정점 2로의 back edge가 발견되어 또 다른 사이클이 형성됩니다. 최종적으로 정점 2에서 count는 2가 되어 flag가 false로 설정되고, 이 그래프는 선인장이 아니라고 판단됩니다.

💻 소스 코드 분석

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

int V, E, A, B;
bool flag = true;  <em>// 선인장 여부를 저장하는 전역 변수</em>
int dfs_num[MAX_N+1], dfs_low[MAX_N];  <em>// DFS 넘버링과 low 값</em>
int vis[MAX_N+1];  <em>// 방문 상태: 0(미방문), 1(방문중), 2(완료)</em>
int dfs_number = 0;  <em>// DFS 넘버링을 위한 전역 카운터</em>
vector<int> G[MAX_N+1];  <em>// 인접 리스트로 구현된 그래프</em>

void dfs(int node, int parent) {
    <em>// 현재 노드에 DFS 번호 할당 및 low 값 초기화</em>
    dfs_num[node] = dfs_low[node] = ++dfs_number;
    vis[node] = 1;  <em>// 현재 방문 중임을 표시</em>
    int count = 0;  <em>// 현재 노드가 참여하는 사이클의 개수</em>
    
    <em>// 모든 인접 정점에 대해 탐색</em>
    for (auto &x : G[node]) {
        if (vis[x] == 0) {  <em>// 아직 방문하지 않은 정점</em>
            dfs(x, node);  <em>// 재귀적으로 DFS 수행</em>
            
            <em>// 자식으로부터 돌아온 후, 브리지가 아닌지 확인</em>
            if (dfs_low[x] <= dfs_num[node]) {
                count++;  <em>// 현재 노드가 새로운 사이클에 참여</em>
            }
            <em>// 현재 노드의 low 값을 자식의 low 값으로 업데이트</em>
            dfs_low[node] = min(dfs_low[node], dfs_low[x]);
            
        } else if (x != parent) {  <em>// 이미 방문된 정점이지만 부모가 아님</em>
            <em>// back edge 또는 forward/cross edge 처리</em>
            dfs_low[node] = min(dfs_low[node], dfs_num[x]);
            
            if (vis[x] == 1) {  <em>// back edge인 경우 (아직 방문 중인 조상)</em>
                count++;  <em>// 새로운 사이클 발견</em>
            }
        }
    }
    
    <em>// 현재 노드가 2개 이상의 사이클에 참여하면 선인장이 아님</em>
    if (count >= 2) flag = false;
    vis[node] = 2;  <em>// 방문 완료로 표시</em>
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    memset(vis, 0, sizeof(vis));  <em>// 방문 배열 초기화</em>
    cin >> V >> E;
    
    <em>// 간선 정보를 읽어서 인접 리스트 구성</em>
    for (int i = 0; i < E; ++i) {
        cin >> A >> B;
        G[A].push_back(B);
        G[B].push_back(A);  <em>// 무방향 그래프이므로 양방향 연결</em>
    }
    
    dfs(1, -1);  <em>// 정점 1부터 DFS 시작 (부모는 -1)</em>
    
    <em>// 결과 출력</em>
    cout << (flag ? "Cactus" : "Not cactus");
    return 0;
}

이 코드의 핵심은 각 정점에서 count 변수를 통해 해당 정점이 참여하는 사이클의 개수를 정확히 세는 것입니다. DFS의 구조적 특성과 back edge 감지를 활용하여 복잡한 사이클 열거 없이도 선인장 조건을 효율적으로 검증할 수 있습니다.

📌 핵심 개념 정리

이 문제의 해결책은 복잡한 사이클 구조를 직접 분석하지 않고, DFS의 구조적 정보를 활용해 각 정점의 사이클 참여도를 간접적으로 계산하는 것이었습니다. 선인장의 정의를 “각 정점이 최대 하나의 사이클에만 속한다”로 이해하고, 이를 DFS 탐색 과정에서 효율적으로 검증하는 방법을 찾아낸 것이 핵심입니다.

특히 dfs_low 값과 back edge의 개념을 활용하여 시간 복잡도 O(V + E)로 문제를 해결할 수 있었으며, 이는 그래프 알고리즘에서 DFS가 가진 강력함을 잘 보여주는 사례입니다.

Similar Posts