[백준] 9466번: 텀 프로젝트

📌 문제

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

📌 설명

DFS 를 통해 사이클을 찾는 방법을 사용하는 문제이다.

위 그림에서 A, B, C는 팀 생성이 불가능하며, 나머지는 팀 생성이 가능하다. DFS의 시작 노드를 start, DFS 수행 중 이미 방문한 노드를 처음 만났을 때 해당 노드를 cur 이라고 한다면, start 부터 cur 이전까지는 팀 생성이 불가능하다. 단, start와 cur이 같은 경우는 본인이 본인을 선택하는 경우이므로, 그냥 넘어간다.

📌 코드

#include <iostream>

using namespace std;

int arr[100001];
int visited[100001]; // 0: 방문X, 1: 팀 생성 가능, -1: 팀 생성 불가능
int n, start;

void dfs(int i) {
	// 순환: x에서 시작, y가 순환의 시작 => x부터 y 전까지 visited를 -1로 변경
	// 단 x와 y와 같은 경우 pass
	// 순환 발생 여부: 접근하려고 하는 사람이 이미 방문한(y) 경우

	if (visited[i]) {
		if (i == start)
			return;
		while (start != i) {
			visited[start] = -1;
			start = arr[start];
		}
		return;
	}

	visited[i] = 1;
	dfs(arr[i]);
}

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

	int T;
	cin >> T;
	while (T--) {
		cin >> n;
		for (int i = 1;i <= n;i++) {
			cin >> arr[i];
		}

		for (int i = 1;i <= n;i++) {
			start = i;
			if (visited[i] == 0) {
				dfs(i);
			}
		}

		int cnt = 0;
		for (int i = 1;i <= n;i++) {
			if (visited[i] != 1)
				cnt++;
			visited[i] = 0;
		}

		cout << cnt << "\n";
	}
}

---

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)

def dfs(cur,start,arr,visited):
    # 이미 방문한 경우
    if visited[cur]:
        # 본인이 본인을 선택한 경우
        if cur==start:
            return
        
        # start부터 cur 이전까지는 팀 생성 불가능
        while start!=cur:
            visited[start]=-1
            start=arr[start]

        return
    
    visited[cur]=1
    dfs(arr[cur],start,arr,visited)

T = int(input())

for _ in range(T):
    n=int(input())
    arr = [0] + list(map(int, input().split()))

    # 0: 방문 X, 1: 팀 생성 가능, -1: 팀 생성 불가능
    visited=[0]*(n+1)

    for i in range(1, n+1):
        if visited[i]==0:
            start=i
            dfs(i,start,arr,visited)

    cnt=0
    for i in range(1, n+1):
        if visited[i]!=1:
            cnt+=1

    print(cnt)