[백준 알고리즘] 9466번: 텀 프로젝트

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

문제

문제

이번 가을학기에 ‘문제 해결’ 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, …, sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,…, sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

풀이

그래프의 사이클을 확인하는 문제였다. 처음에는 아무 생각없이 유니온 파인드로 풀어야겠다고 생각했다가 유향 그래프에서는 유니온 파인드를 사용할 수 없다는 것을 깨닫고 다시 코드를 작성했다.

이 문제에서 가장 어려웠던 부분이 사이클을 확인하는 작업을 빠른 시간 안에 마치는 것이다. N^2 도 시간 초과가 난다. 나는 사이클을 찾기 위해 몇가지 시도를 해보았다.

1. 사이클이 생기면 역으로 돌아오면서 거쳐온 정점을 세기.

   • 완전히 잘못된 논리였다. 만약 1 -> 3 -> 3 이 있다면, 1이 경로에 포함되기 때문에 엉뚱한 정점까지 사이클에 포함된다고 판단해버린다.

2. 사이클을 다시 한번 돌아보면서 사이클에 있는 정점 세기.

   • 사이클이 발생하면 해당 지점을 start로 두고 다시 start로 돌아올 때까지 돌면서 정점의 개수를 세어보는 방법이다. 이 방법을 사용해서 제출했더니 시간초과를 받았다.

3. 몇번 이동했는지를 기록하면서 체크하는 방법

   • 하다하다 안돼서 인터넷 블로그를 몇개 찾아보니 생각지도 못한 방법이 있었다. 어떤 출발 정점에서부터 탐색하는 정점이 몇번째로 방문하는지 세어보면 중간에 사이클이 발생하더라도 사이클 내에 있는 정점의 개수가 몇개인지 간단한 수학 연산을 통해 알아낼 수 있다. 예를 들어 1 -> 3 -> 3 이 있다면, 시작점은 count 0, 3은 count 1 일때 마지막 정점의 3이 사이클임을 알게 된다. 따라서 현재 사이클을 시작하는 지점과 사이클을 확정하는 직전 지점의 count를 빼고 1을 더하면 사이클에 포함된 정점의 개수를 알게된다.

   좀 더 여러가지 예를 들어보자.

   • 1 -> 3 -> 3 은 사이클 확정 직전 지점은 3에서 count가 1이고, 3의 이웃정점을 확인했을 때 다음 정점이 3임을 알게되기 때문에 3이 가진 count인 1을 직전 정정의 count와 빼준다. 따라서 1->3->3 에서 사이클을 이루는 정점의 개수는 1 - 1 + 1 = 1 이 된다.
   • 1 -> 4 -> 7 -> 6 -> 4 의 경우도 마찬가지이다. count는 1 = 0, 4 = 1, 7 = 2, 6 = 3 이다. 따라서 사이클이 발생하는 직전지점인 6과 사이클의 시작지점인 4의 count 를 이용하면, 3 - 1 + 1 = 3 로 총 세 개의 정점이 사이클에 포함되어 있음을 확인할 수 있다.

사실 3번 방법을 사용하면 O(N)만에 헤결 할 수 있을 줄 알았는데 시간초과를 받았다. 그래서 문제점을 찾아보던 중, 어차피 정점은 항상 한쌍을 만드는데 adjacency list를 만들고 for 문을 넣어둔 것을 발견했다. 바로 변수로 할당하는거나 for문을 한번 도는거나 시간이 비슷할 줄 알았는데, 반복문 탈출을 위해서는 반복문을 무조건 2번 돌아야하니 바로 변수로 선언하는 것 보다 두배 더 오래걸린다. 아주 간단한 부분이었는데, 놓친게 아쉽다.

코드

' '
#include <cstdio>
#include <vector>

using namespace std;

const int MAX = 100001;
bool visited[MAX];
bool searchDone[MAX];
int stepCount[MAX];
int cnt = 0;

void dfs(int now, int origin, int adj[MAX][1]){
    visited[now] = true;
    int next = adj[now][0];

    if (!visited[next]){
        stepCount[next] = stepCount[now] + 1;
        dfs(next, origin, adj);
    }
    else if (!searchDone[next]) {
        cnt += (stepCount[now] - stepCount[next] + 1);
    }

    searchDone[now] = true;
}

int main (){
    int T;
    scanf("%d", &T);

    while(T--){
        int students;
        scanf("%d", &students);

        int selections[MAX][1];

        for (int i = 0 ; i <= students ; i++){
            visited[i] = false;
            searchDone[i] = false;
            stepCount[i] = 0;
        }

        for (int i = 1 ; i <= students ; i++){
            scanf("%d", &selections[i][0]);
        }


        for (int i = 1 ; i <=students ; i++){
            if (!visited[i]){
                dfs(i, i, selections);
            }
        }

        printf("%d\n", students - cnt);
        cnt = 0;
    }
}