백준 9466 - 텀 프로젝트(C++)

 문제 링크입니다. https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

DFS를 이용해 푸는 문제입니다.

사이클이 이루어져 있을 때, 이를 어떻게 찾는지 물어보는 문제입니다.

 

문제를 해석했을 때, 가장 쉬운 접근은

"X번부터 사이클이 존재한다면, 도착점도 X번이니 DFS를 통해서 X가 X에 도착할 수 있는지를 확인하면 된다." 입니다.

하지만, N의 값이 100,000 이하이기에 모든 점들을 DFS탐색 하기에는 시간이 부족합니다.

 

따라서 사이클을 확인하는 것이 아닌, 사이클을 확인했을 때, 사이클에 속하는 점들을 한번에 없애주는 방법이 필요합니다.

 

방법은 다음과 같습니다.

1. 자신이 원하는 학생을 확인한다. 

2. 해당 학생을 이전에 방문하지 않았다면, 해당 학생으로 탐색을 다시 시작해본다.

3. 처음 탐색값을 만났다면 해당 학생이 이전에 사이클로 확인됐던 학생인지 확인합니다.

4. 전에 사이클로 확인하지 않았던 학생이라면 연결된 학생들을 탐색하면서 변수 값을 증가합니다.

해당 과정을 거치면 사이클 확인이 됩니다.

 

문제 예시를 통해 확인해보겠습니다.

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

1번 학생을 먼저 탐색합니다. 3번 학생을 만나고, 3번 학생으로 탐색을 다시 합니다.

3번 학생이 원하는 학생은 자신이니, 사이클을 만족하게 됩니다. 따라서 3->3까지의 사이클을 확인합니다.

 

2번 학생을 탐색합니다. 1번 학생은 이전에 탐색했으니, 2번 학생은 사이클이 안되는 것을 알 수 있습니다.

 

4번 학생 -> 7번 학생 -> 6번 학생으로 탐색을 진행합니다. 6번 학생이 원하는 학생이 4번이니, 처음 탐색값을 만난 것을 확인할 수 있습니다. 

이때, 6 -> 4로 사이클 탐색을 하는 것이 아닌, 4 -> 6으로 사이클 탐색을 해야합니다. 

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>
#include <stack>
#define P pair<int,int>
#define LL long long

using namespace std;

int test_case;
int N;
int connect[100001];
bool check[100001];
bool Fin[100001];
int cycle;

void dfs(int x){
    check[x] = true;
    int xx = connect[x];
    if(!check[xx]) dfs(xx);
    else if(!Fin[xx]){
        for(int i = xx; i != x; i = connect[i]){
            cycle++;
        }
        cycle++; // 자신 추가
    }
    Fin[x] = true;
}

void solve(){
    memset(check, false, sizeof(check));
    memset(Fin, false, sizeof(Fin));
    cycle = 0;
	for(int i = 1; i <= N; i++){
	    if(!check[i]) dfs(i);
	}
	cout << N - cycle << "\n";
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for(int k = 0; k < test_case; k++){
	    cin >> N;
	    for(int i = 1; i <= N; i++){
	        cin >> connect[i];
	    }
	    solve();
	}
	return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요