[백준] 9466 - 텀 프로젝트

1. 문제

9466번: 텀 프로젝트

2. 개요

학생들이 프로젝트 수행을 위해 프로젝트를 같이 하고 싶은 팀원을 한 명씩 선택한다.

본인이 본인을 선택 할 수 도 있다.

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

이 때 팀을 이루지 못한 학생의 수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

그래프에서 사이클이 형성되지 않은 정점의 개수를 구하면 된다.

방문하지 않은 정점마다 방문처리를 해 가며 DFS로 탐색한다.

DFS를 시작할 때 group이라는 새 큐를 만들고 탐색하는 정점은 이 큐에 하나씩 넣어준다.

DFS로 순회하던 중 다음 방문할 곳이 이미 방문된 곳이라면 사이클이 형성되었다는 이야기가 된다.

또한 다음 방문지를 사이클의 첫 정점으로도 해석할 수 있다.

그러므로 group에서 다음 방문지가 첫 정점이 될 때 까지 앞의 원소들을 모두 빼내준 뒤,

group의 수 만큼 그룹을 형성한 사람 수를 늘려준다.

모든 정점을 탐색 완료했다면 N에서 그룹을 형성한 사람 수를 뺀 값을 출력한다.

3-2. Python

import sys
from collections import deque

sys.setrecursionlimit(100000)

def dfs(idx, group):
    global answer
    if visited[picks[idx] - 1] == 1:
        while group and group[0] != picks[idx] - 1:
            group.popleft()

        answer += len(group)

    else:
        visited[picks[idx] - 1] = 1
        group.append(picks[idx] - 1)
        dfs(picks[idx] - 1, group)

T = int(sys.stdin.readline())

for t in range(T):
    answer = 0
    N = int(sys.stdin.readline())

    picks = list(map(int, sys.stdin.readline().split()))
    visited = [0 for i in range(100000)]

    for i in range(N):
        if visited[picks[i] - 1] == 0:
            visited[i] = 1
            dfs(i, deque([i]))

    print(N - answer)

3-3. C#

namespace boj_9466
{
    internal class Program
    {
        static int answer;
        static bool[] visited;
        static int[] picks;

        static void Main(string[] args)
        {
            int T = int.Parse(Console.ReadLine());

            for (int t = 0; t < T; t++)
            {
                answer = 0;

                int N = int.Parse(Console.ReadLine());

                picks = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                visited = new bool[N];

                for (int i = 0; i < N; i++)
                {
                    if (visited[picks[i] - 1] == false)
                    {
                        Queue<int> q = new Queue<int>();
                        q.Enqueue(i);
                        visited[i] = true;
                        DFS(i, q) ;
                    }
                }

                Console.WriteLine(N - answer);
            }
        }

        static void DFS(int idx, Queue<int> group)
        {
            if (visited[picks[idx] - 1])
            {
                while (group.Count > 0 && group.Peek() != picks[idx] - 1)
                {
                    group.Dequeue();
                }

                answer += group.Count;
            }

            else
            {
                visited[picks[idx] - 1] = true;
                group.Enqueue(picks[idx] - 1);
                DFS(picks[idx] - 1, group);
            }
                
        }
    }
}