[백준] 9466: 텀 프로젝트

0. 문제 주소

 

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

 

1. 풀이

 

DFS로 사이클 구하는 연습 용으로 풀어 본 문제.

사이클이 발생했냐를 판단하는 기준으로 두 가지 배열을 사용한다.

bool visited[MAX];
bool finished[MAX];

visited는 흔히 그래프 순회에서 방문 여부를 체크하는 배열인데, 이 문제에선 finished라는 배열을 추가로 사용한다.

그 이유를 알기 위해서 DFS가 동작하는 원리에 대해서 생각해보자.

 

정점 A 에서 시작하는 DFS가 호출되었을 때, A와 인접한 정점들에 대해서 각각 DFS가 재귀적으로 호출된다. 그럼 맨 처음에 A에서 시작한 DFS가 완전히 끝나는 때는 언제일까?

당연히 "A와 인접한 정점들에서 시작하는 DFS가 모두 끝날 때"이다. 

 

이것을 염두해두고, 우리는 DFS를 이용하여 사이클을 찾는 것이 목표이므로 이번엔 사이클이 발생할 때 어떤 일이 일어나는지 생각해보자.

편의를 위해 A -> B, B -> C, C -> A 형태의 사이클이 있다고 가정하자.

DFS(A)를 호출하면, A와 인접한 B에 대해 DFS(B)가 호출되고, 마찬가지로 DFS(C)가 호출된다. 

그 다음엔? C와 인접한 A를 방문해야 하는데, A는 이미 방문했다고 표시를 해 놓았을 것이다.

 

일반적인 DFS라면 여기서 DFS(C)가 바로 종료되겠지만, 사이클을 찾는 것이 목표이기 때문에 주목해야 할 부분이 있다.

바로 DFS(A)가 완전히 종료되지 않았다는 것이다.

실마리가 잡히니 정리를 해보자.

 

사이클이 발생했다고 어떻게 알 수 있을까?

다음 방문할 정점이 이미 방문한 상태이지만, "그 정점에서 시작된 DFS는 아직 끝나지 않았을 때"

라고 정리할 수 있다.

정리해보면 DFS 함수를 다음과 같이 작성할 수 있다.

 

void DFS(int u){
    visited[u] = true;
    int v = E[u];
    if (visited[v]){
        if (!finished[v]){
            cnt++;
            for (int start = v; start != u; start = E[start]){
                cnt++;
            }
        }
    }
    else{
        DFS(v);
    }
    finished[u] = true;
}

 

int v = E[u];

다음 방문할 정점을 위와 같이 설정한 것은 문제의 특성상 모든 정점의 outdegree가 1이기 때문에,

E[u] = ( u가 가르키는 정점 ) 으로 E를 설정했기 때문이다.

 

2. 풀이 코드

 

* 유의할 점

1. 모든 정점의 outdegree가 1이기 때문에 굳이 vector 배열을 사용하지 않아도 된다.

2. 사이클이라고 판단되었을 때, 사이클의 길이를 체크해준다.

3. 전체 정점 개수 - 사이클에 포함된 정점 개수 = 정답

 

#include <bits/stdc++.h>
#define MAX 100005

using namespace std;

int T;
int E[MAX];
int cnt;
bool visited[MAX];
bool finished[MAX];

void DFS(int u){
    visited[u] = true;
    int v = E[u];
    if (visited[v]){
        if (!finished[v]){
            cnt++;
            for (int start = v; start != u; start = E[start]){
                cnt++;
            }
        }
    }
    else{
        DFS(v);
    }
    finished[u] = true;
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%d", &T);
    for (int x=0;x<T;x++){
        int n;
        scanf("%d", &n);

        cnt = 0;
        fill(visited+1, visited+n+1, 0);
        fill(finished+1, finished+n+1, 0);

        for (int u=1;u<=n;u++){
            int v;
            scanf("%d", &v);
            E[u] = v;
        }
        for (int u=1;u<=n;u++){
            if (!visited[u]){
                DFS(u);
            }
        }
        printf("%d\n", n - cnt);
    }
}