BOJ 9466 텀 프로젝트

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

9466번: 텀 프로젝트

그래프에서 사이클이나 루프를 이루지 않는 노드의 개수를 세면 되는 문제입니다. 문제를 읽고 이걸 파악하는 것은 어렵지 않지만, 시간초과가 뜨지 않게끔 구현하는 것은 꽤 까다롭다고 할 수 있습니다.

 

각 학생을 vertex라고 하고, 학생이 프로젝트를 같이 하고 싶어하는 다른 학생을 방향성 있는 edge로 표현하여 그래프를 만들 수 있습니다.

 

 

위와 같은 그래프가 있다고 해봅시다. 학생1은 학생2를 선호하고, 학생2는 학생3을 선호하는 등의 상황입니다.

눈으로는 사이클이나 루프가 아닌 노드를 금방 파악할 수 있습니다. 1번, 5번 노드입니다.

 

알고리즘 상으로는 어떻게 찾을까요? 잘 모르겠으니, 1번 노드부터 그래프 탐색을 해봅시다. 단, 탐색 중에 만난 노드에는 "1"이라는 표시를 해줍시다. 이는 1번 노드에서 시작된 탐색 중에 만났다는 표시입니다. 또한 탐색 중 만난 노드가 총 몇 개인지도 기록해봅시다.

 

 

그런데 탐색을 하다보니 노드4가 노드2를 지목하고 있어서 사이클이 형성되었습니다. 탐색을 무한으로 돌리면 2, 3, 4노드로 형성된 사이클을 계속 돌 것 같네요. 그런데 우리는 지금 사이클을 발견한 겁니다. 즉, 다음으로 탐색할 노드가 이미 방문한 노드이면 사이클을 형성한 것입니다. 사이클을 이루는 노드의 수는 어떻게 구할까요? 우리는 탐색을 하면서 노드의 개수를 기록해왔기 때문에, 노드4와 노드2에 기록된 cnt 값을 통해 그 개수를 구할 수 있습니다. 여기선 (4-2)+1개가 되겠네요(코드 상으론 약간 다르지만, cnt를 이용함이 핵심입니다).

 

노드2, 3, 4는 서로 팀을 이루겠군요. 노드1에서의 탐색이 끝났으니, 노드2에서 탐색을 해 볼 차례입니다. 그런데 노드2는 이미 방문된 상태입니다. 그러므로 탐색할 필요가 없습니다. 노드3, 4도 마찬가지입니다. 그렇다면 노드5에서 탐색을 해 볼 차례입니다.

 

 

노드5에서 탐색을 시작했다는 의미로, labal에 5를 적고 cnt를 1로 기록했습니다. 다음 노드를 탐색하려고 보니, 노드3입니다. 그런데 노드3은 이미 방문된 상태입니다(label과 cnt가 이미 적혀 있습니다). 방문한 노드를 만났으니 탐색은 멈춰야 합니다. 그런데 노드5는 label이 5인 반면, 노드3의 label은 1입니다. 즉, 사이클을 형성하지 않았습니다. 이 경우 노드5는 팀을 이룰 수 없습니다.

 

이제 노드6에서 탐색할 차례입니다.

 

 

 

노드6에 label = 6, cnt = 1를 기록하고 탐색을 시작합니다. 그런데 노드6은 노드6을 지목하고 있습니다. 이 경우도 이미 방문한 노드를 만났다고 볼 수 있습니다. 자기 자신에 기록된 label끼리 비교하니, 당연히 같습니다(이 경우 루프입니다). 노드6은 혼자서 팀을 이룰 수 있겠군요.

 

그래프에 있는 모든 노드를 방문했습니다. 최종적으로 팀을 이룬 노드들, 즉 사이클이나 루프인 노드들은 노드2, 3, 4, 6입니다. 전체 노드가 6개이니, (6-4)=2가 답입니다.

 

이 알고리즘을 코드로 구현하면 다음과 같습니다.

 

 

#include <iostream>
#include <queue>
#include <utility>
#include <algorithm>
using namespace std;
int mypick[100001];
int vis[100001][2];

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

    int TS;
    cin >> TS;
    for (int ts = 0; ts < TS; ts++) {
        int N;
        cin >> N;
        fill(vis[0], vis[0]+(100001*2), 0);
        int lonely_student = N;
        
        for (int i = 1; i <= N; i++) {
            cin >> mypick[i];
        }
        for (int i = 1; i <= N; i++) {
            if (!vis[i][0]) {
                int cnt = 1;
                vis[i][0] = cnt;
                vis[i][1] = i;
                int cur = mypick[i];
                while (true) { // 탐색 과정
                    ++cnt;
                    // 이미 방문한 노드를 만난 경우
                    if (vis[cur][0]) {
                    	// 그 노드의 label을 보고 사이클 혹은 루프인지 결정한다
                        if(vis[cur][1] == i) lonely_student -= (cnt - vis[cur][0]);
                        break;
                    }
                    vis[cur][0] = cnt;
                    vis[cur][1] = i;
                    cur = mypick[cur];
                }
            }
        }
        cout << lonely_student << "\n";
    }
}

 

 

Reference

https://lmcoa15.tistory.com/51

백준 9486번 - 텀 프로젝트