[백준/파이썬][Gold III] 텀 프로젝트 - 9466

[Gold III] 텀 프로젝트 - 9466

문제 링크

성능 요약

메모리: 238560 KB, 시간: 1016 ms

분류

깊이 우선 탐색, 그래프 이론, 그래프 탐색

제출 일자

2025년 2월 10일 16:55:40

문제 설명

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s₁, s₂, ..., s_r)이라 할 때, r=1이고 s₁이 s₁을 선택하는 경우나, s₁이 s₂를 선택하고, s₂가 s₃를 선택하고,..., s_r-1이 s_r을 선택하고, s_r이 s₁을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

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

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

풀이

1. 스택

def main() :
    n = int(input())
    arr = [0] + list(map(int, input().split()))

    visited = [0] * (n + 1)
    finished = [0] * (n + 1)
    cnt = 0

    for i in range(1, n + 1) :
        if visited[i] :
            continue

        # 각 DFS마다 현재 경로를 기록
        stack = []
        cur = i

        while True :
            visited[cur] = 1
            stack.append(cur)
            nxt = arr[cur]

            # 아직 방문하지 않았다면 계속 진행
            if not visited[nxt] :
                cur = nxt
                continue

            # 방문한 적은 있지만, DFS 처리가 끝나지 않은 경우 => 현재 경로에 있으므로 사이클 발견
            if not finished[nxt] :
                # 스택에서 nxt가 처음 등장한 인덱스를 찾고, 그 이후의 노드들이 사이클에 속함
                idx = stack.index(nxt)
                cnt += len(stack) - idx
            # 더 이상 진행할 수 없으므로 탈출
            break

        # 현재 DFS 경로에 있는 모든 노드에 대해 finished 처리
        for node in stack :
            finished[node] = 1

    print(n - cnt)

T = int(input())
for _ in range(T) :
    main()

2. 재귀

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

def main() :
    n = int(input())
    arr = [0] + list(map(int, input().split()))

    visited = [0] * (n + 1)
    finished = [0] * (n + 1)
    cnt = 0

    def dfs(v) :
        nonlocal cnt
        visited[v] = 1
        nxt_v = arr[v]
        # 아직 방문하지 않은 학생이면 DFS 재귀 호출
        if not visited[nxt_v] :
            dfs(nxt_v)

        # 이미 방문한 학생인데, 아직 DFS 처리가 끝나지 않았다면 사이클(팀)을 발견
        elif not finished[nxt_v] :
            tmp = nxt_v
            # 사이클에 포함되는 학생들을 센다
            while tmp != v :
                cnt += 1
                tmp = arr[tmp]
            cnt += 1    # 현재 v도 사이클에 포함
        finished[v] = 1 # DFS 처리 완료

    for i in range(1, n + 1):
        if not visited[i] :
            dfs(i)

    print(n - cnt)

T = int(input())
for _ in range(T) :
    main()

처음에 스택으로 풀이를 진행했을 때, RecursionError가 나와서 스택으로 풀이하였다. 재귀로 풀 경우 sys.setrecursionlimit(10 ** 5)로 세팅해주면 통과할 것이지만, 딱 저 값만 통과되니 참고하길 바란다.