백준/9466번/텀 프로젝트/골드3

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

문제 설명

Site: Baekjoon
Number: 9466
Category: DFS
Rank: Gold 3

각 숫자 마다 다른 숫자를 가르킬 때, 사이클이 형성된다면 사이클에 포함되는 인원을 빼고 남는 인원 수를 출력하는 문제입니다. 사이클은 여러개가 존재할 수 있습니다.

문제 풀이

DFS방법에 Queue를 합쳐 해결하였습니다.

1. 방문 기록이 있는 점이라면 무시합니다.

2. 한 점에서 방문 기록이 있는 점까지 계속 Queue에 원소를 넣어 방문하며 마지막에 접근한 점을 기록합니다.

3. 기록되어 있는 점 부터 사이클이 시작됨으로, 기록된 점이 나올 때까지 Queue에서 원소를 뺍니다.

4. Queue에 남아있는 원소의 크기가 사이클이 형성된 점의 수이므로 이를 총 점의 갯수에서 제외합니다.

5. 위의 과정을 모든 점을 돌며 진행합니다.

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

int students[100001];
bool visited[100001];

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

    int T;
    cin >> T;

    while(T--)
    {
        int N, ans;
        cin >> N;

        ans = N;

        for (int i = 1; i < N+1; i++)
            cin >> students[i];

        memset(visited, false, sizeof(visited));

        for(int i = 1; i < N+1; i++)
        {
            if(visited[i])
                continue;

            queue<int> q;
            int cur = students[i];

            visited[i] = true;
            q.push(i);

	        while(visited[cur] == false)
	        {
                q.push(cur);
                visited[cur] = true;
                cur = students[cur];
	        }

            while(!q.empty())
            {
                int front = q.front();
                if (front == cur)
                    break;
                q.pop();
            }
            ans -= q.size();
        }

        cout << ans << '\n';
    }

    return 0;
}