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

📩 출처

문제

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

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

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

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

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

입력

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

출력

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

👉 생각

• 재귀를 통한 깊이 우선 탐색을 하면서 사이클을 만들었다. 사이클이 만들어지거나 자기 자신을 선택한 번호라면 visited의 값을 1로 바꿔준다.
• 재귀의 깊이를 정하고 마지막에 visited에서 인덱스가 0인 곳을 빼고 0의 갯수를 출력한다.

import sys
sys.setrecursionlimit(10000000)

def dfs(start, cnt):
    global i

    if cnt > 0 and start == i:
        return True

    if not visited[start]:
        visited[start] = 1
        check = dfs(students[start], cnt + 1)
        if not check:
            visited[start] = 0
        else:
            return True

t = int(input())
for _ in range(t):
    n = int(input())
    students = [0] + list(map(int, sys.stdin.readline().split()))
    visited = [0 for _ in range(n+1)]
    for i in range(1, n+1):
        if not visited[i]:
        	dfs(i, 0)

    print(visited.count(0) - 1)

• 그렇지만 위의 코드는 82%에서 시간 초과가 발생한다. 위 코드 같은 경우 하나의 사이클이 생성되면 그 사이클 내부에 있는 숫자는 따로 깊이 우선 탐색을 하지 않는다.
• 그러나, 사이클을 이루지 못한 숫자가 자기 자신을 선택한 숫자를 바라 보았을 때 위 코드는 각각 깊이우선 탐색을 하게 되어 있다.
• 사이클을 이루지 못하는 숫자가 자기 자신을 선택한 숫자를 바라볼 때 한번에 그 숫자도 체크를 해주어야 하는 것 같다.
• 따라서 res라는 배열을 global로 두고 사이클을 이루거나, 자기 자신을 선택한 숫자가 있다면 추가를 해준다.
• 싸이클을 이루었을 때 check라는 배열을 그대로 더하는게 아니라 인덱싱을 하는 이유는,자기 자신을 선택한 숫자가 포함되었을 경우를 체크해준다.

import sys
sys.setrecursionlimit(10000000)

def dfs(start):
    global res
    visited[start] = 1
    check.append(start)
    new = students[start]

    if visited[new]:
        if new in check:
            res += check[check.index(new):]
        return
    else:
        dfs(new)

t = int(input())
for _ in range(t):
    n = int(input())
    students = [0] + list(map(int, sys.stdin.readline().split()))
    visited = [0 for _ in range(n+1)]
    res = []
    for i in range(1, n+1):
        if not visited[i]:
            check = []
            dfs(i)

    print(n - len(res))