[백준/C++]#9466 - 텀 프로젝트

풀이

#include <iostream>
using namespace std;

int a[100001];
int check[100001];
int numb[100001];

int dfs(int node, int len, int num) {
	if (check[node] != 0) {		// 사이클의 시작부분일 때
		if (num != numb[node]) {	// 지금 고유번호와, 사이클 고유번호가 다르면
			return 0;
		}
		else return len-check[node];	// 사이클 길이 출력
	}
	check[node] = len;		// 길이 대입
	numb[node] = num;		// 고유번호 대입
	return dfs(a[node], len+1, num);	// 탐색 순환
}

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i=1; i<=n; i++) {	// 입력 및 배열 초기화
			cin >> a[i];
			check[i]=0;
			numb[i]=0;
		}
		int ans = 0;
		for (int i=1; i<=n; i++) {	// 사이클의 총 길이 구하기
			if (check[i] == 0) {
				ans += dfs(i,1,i);
			}
		}
		cout << n-ans << '\n';
	}
	return 0;
}

풀이

문제에서 알아내야하는 것은 만들어지는 사이클의 총 길이이다.

예상되는 탐색 결과는 다음과 같다.

①사이클 탐색완료

②사이클이 아님 (사이클이 시작되는 지점에서 탐색 종료)

 

문제는 이 둘을 구분하는 것(사이클/ 비사이클)이 기존 dfs로 불가능하다는 것이다.

결국 모든 탐색의 종료는 사이클이 시작되는 시점이다.

다만 사이클은 한번 순환하고 종료가 되고, 비사이클은 순환 전에 종료된다.

 

이 둘의 비교를 위해 numb 배열이 필요하다.

각 탐색마다의 고유번호를 만들어서, 내 탐색 고유번호가 사이클의 고유번호와 일치하면 사이클로 인정한다.

이때 사이클 길이를 반환하고, 고유번호가 다르면 0을 반환한다.

고유번호는 for 문안에서의 i 즉 index 값을 활용한다.

 

사이클의 길이를 구하기 위해 또 다른 배열이 필요하다.

이는 각 dfs가 반복될 때마다 +1 되어 사이클의 길이를 저장할 수 있다.

기존의 check 배열을 활용한다.

 

지금의 길이(len) - 사이클이 시작되는 시점 (check[node])을 하면 사이클의 길이가 구해진다.

---

+a

 

 

다른풀이(from 백준github)

#include <cstdio>
int a[100001];
int d[100001];
int s[100001];
int n;
int dfs(int x, int cnt, int &step) {
    while (true) {
        if (d[x] != 0) {
            if (step != s[x]) {
                return 0;
            }
            return cnt-d[x];
        }
        d[x] = cnt;
        s[x] = step;
        x = a[x];
        cnt += 1;
    }
}
int main() {
    int t;
    scanf("%d",&t);
    while (t--) {
        scanf("%d",&n);
        for (int i=1; i<=n; i++) {
            scanf("%d",&a[i]);
            d[i] = 0;
            s[i] = 0;
        }
        int ans=0;
        for (int i=1; i<=n; i++) {
            if (d[i] == 0) {
                ans += dfs(i, 1, i);
            }
        }
        printf("%d\n",n-ans);
    }
    return 0;
}

반복문을 사용한 답안이다.

while (true)를 통해 계속 반복되는 루프를 만들고, return문을 사용해 탈출하는 방식이 독특하다.