[DFS] 9466번 텀 프로젝트

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번으로 표현할 때, 선택의 결과는 다음과 같다.

1	2	3	4	5	6	7
3	1	3	7	3	4	6

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

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

 

입력

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

 

출력

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

 

예제 입력

2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8

 

예제 출력

3
0

 

해결방법

⭐️ 1차 시도 ⭐️

시간 초과

 

처음에 생각했던 솔루션은 이러하다

1. 첫번째 학생부터 마지막 학생까지 DFS 탐색을 수행한다
2. 현재 학생을 vector에 담고 희망하는 학생의 인덱스를 통해 재귀함수를 수행한다
3. 재귀를 수행하다가 만약 vector에 현재 학생의 인덱스가 있다면 조건을 검사한다
4. 만약 vector의 마지막과 첫번째가 일치한다면 사이클이고 일치하지 않는다면 사이클이 아니다
5. vector를 초기화 한 후, 다음 학생부터 다시 DFS 탐색을 수행한다

 

이 문제에서 n의 조건은 n≦100,000 이다

이 때, 최악의 경우 각 학생은 나머지 학생 모두를 탐색할 수 있기 때문에 O(n²) 의 시간복잡도이다

따라서 10,000,000,000으로 시간 초과가 발생할 수 밖에 없다

 

 

⭐️ 2차 시도 ⭐️

맞았습니다!!

Moon 님의 블로그

 

거의 코드를 흡수하듯이 봤다

솔직히 솔루션이 떠오르지 않아서 너무 막막했기에 다른 사람의 솔루션과 코드를 참고하는 방법밖에 없었다... 꼭 다시 풀어야지....!!!!!

 

블로그에서 너무 친절하게 설명을 해줬다

1. 첫번째 학생부터 DFS 탐색을 수행한다
2. DFS 함수는 (시작노드, 현재노드, 카운트) 를 매개변수로 전달한다
3. 방문 시, first 배열에는 시작노드를 visited 배열에는 현재 카운트를 넣어준다
4. 재귀를 수행하다 visited 배열에 이미 값이 들어간 노드를 만났다면 두가지 경우를 검사한다
5. 첫번째 경우는 사이클이 완성된 경우이다. 이 때는 현재 노드의 first 배열을 확인하여 현재 DFS 에서 체크되었는지 확인을 해준다. 이 때는 (현재 노드의 카운트 - visited[현재 노드]) 를 리턴해준다
6. 두번째 경우는 이미 이전의 탐색에서 사이클이 완성되었거나 완성에 실패했던 경우이다. 이때는 더이상 탐색을 할 필요가 없기 때문에 0 을 리턴해준다

 

...정말 내머리에서는 나오지 않을 그런 솔루션이었다... 😢😢

아직은 알고리즘을 풀 때, 공식에 대입하듯 풀이를 하는데 언제쯤 이런 솔루션을 생각할 수 있을까...

 

 

⭐️ 3차 시도 ⭐️

맞았습니다!!

jm25님의 블로그

jaimemin님의 블로그

 

새로운 방법을 찾았다

위에서 말한대로 모든 학생을 반복문으로 돌며 다른 학생들과 비교한다면 O(N²) 이기 때문에 시간 초과가 발생한다

따라서 이미 사이클이 형성되었거나 사이클 형성에 실패한 학생은 탐색을 진행하지 않도록 해야한다

 

이를 해결하기 위해 visited 배열과 finished 배열을 사용한다 !!

1. 첫번째 학생부터 DFS 탐색을 수행한다
2. 방문된 노드는 visited 을 true 로 설정해준다
3. 현재 학생이 가리키는 다음 학생의 visited 값이 True 인 경우와 False 인 경우로 분기한다
4. 아직 방문하지 않은 경우(False) 에서는 계속해서 다음 학생을 기준으로 DFS 탐색을 수행한다
5. 이미 방문한 경우(True) 에서는 사이클이 형성된 경우 인지 이미 형성되거나 실패한 경우 인지 확인을 한다
6. 이는 finished 배열로 알 수 있다! (만약 사이클이 형성된 경우는 finished 배열이 false)
7. 사이클을 돌며 cnt 값을 센 후, +1 을 해주면 사이클을 형성한 학생의 수이다
8. DFS 함수의 마지막에는 finished 배열을 true 로 설정해준다

 

아래의 코드는 사이클을 형성한 학생의 수를 구하는 코드이다

• 만약 1 → 2 → 3 → 1 의 사이클이 형성되었다면, 1 부터 반복문을 돌린다 (now: 3, nxt: 1)
• 사이클의 마지막 노드 전까지 반복하며 cnt++ 을 수행한다
• 마지막 노드를 포함하면 곧바로 종료 되기 때문에 마지막에 cnt에 +1 을 수행해준다

if(!finished[nxt]){
    for(int i=nxt; i!=now; i=student[i]){
        cnt++;
    }
    cnt++;
}

 

 

소스코드

# Solution1

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 100001
#define INF 987654321
using namespace std;

int testcase;
int n,ans;
int student[MAX];
int first_student[MAX];
int visited[MAX];

int dfs(int start,int current,int cnt){
    if(visited[current]){
        
        // 첫번째로 dfs를 시작한 학생이 맞는지, 사이클이 맞는지
        if(first_student[current] != start)
            return 0;
        
        // 사이클에 해당하는 학생 수
        return cnt - visited[current];
    }
    
    first_student[current] = start;
    visited[current] = cnt;
    return dfs(start,student[current],cnt+1);
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    
    for(int t=0; t<testcase; t++){
        cin >> n;
        
        for(int i=1; i<=n; i++){
            cin >> student[i];
        }
        
        memset(first_student, 0, sizeof(first_student));
        memset(visited, 0, sizeof(visited));
        
        ans = 0;
        for(int i=1; i<=n; i++){
            if(!visited[i])
                ans += dfs(i,i,1);
        }
        cout << n-ans << "\n";
    }
}

# Solution2

#include <iostream>
#include <stdio.h>
#include <math.h>
#include <bitset>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 100001
#define INF 987654321
using namespace std;

int testcase;
int n,cnt;
int student[MAX];
bool visited[MAX];
bool finished[MAX];

void dfs(int now){
    visited[now] = true;
    
    int nxt = student[now];
    // 아직 방문하지 않은 경우
    if(!visited[nxt]){
        dfs(nxt);
    }
    // 이미 방문했던 경우
    // 1. 사이클 형성 도중 노드 방문 → 사이클 작업 수행
    // 2. 이미 앞에서 사이클 형성을 시도했던 노드 방문 → 아무 작업도 수행하지 않음
    else{
        // 1번 경우
        if(!finished[nxt]){
            // 만약 1 → 2 → 3 → 1 의 사이클이 형성되었다면
            // 1 부터 반복문을 돌린다 (now: 3, nxt: 1)
            // 사이클의 마지막 노드 전까지 반복하며 cnt++ 을 수행한다
            // 마지막 노드를 포함하면 곧바로 종료 되기 때문에 마지막에 cnt에 +1 을 수행해준다
            for(int i=nxt; i!=now; i=student[i]){
                cnt++;
            }
            cnt++;
        }
    }
    
    // 사이클 형성에 성공하거나 실패하였기 때문에 더이상 탐색 X
    finished[now] = true;
}

int main(int argc, const char * argv[]) {
    // cin,cout 속도향상
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> testcase;
    for(int t=0; t<testcase; t++){
        cin >> n;
        
        for(int i=1; i<=n; i++){
            cin >> student[i];
        }
        
        memset(visited, false, sizeof(visited));
        memset(finished, false, sizeof(finished));
        
        cnt = 0;
        for(int i=1; i<=n; i++){
            // 아직 방문하지 않은 경우
            if(!visited[i]){
                dfs(i);
            }
        }
        cout << n - cnt << "\n";
    }
}