[백준알고리즘] 9466번: 텀 프로젝트 -Python

[백준알고리즘] 9466번: 텀 프로젝트 -Python

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

9466번: 텀 프로젝트

텀 프로젝트 팀을 이상하게 짠다고 한다. 사이클이 형성되는 인원들만 팀을 인정해준다. 이때 사이클에 끼지 못한 학생의 수를 구하는 문제이다.

 

이전에 풀었던 순열 사이클 문제와 비슷해보인다. 순열 사이클에서는 순열이 주어져서 모두가 사이클에 포함되는 경우였다면 여기서는 주어지는 입력이 순열이 아니다.

 

이전 순열 사이클에서 의문을 풀었던 반례들에 대해서 생각을 한다면 쉽게 풀 수 있었던 문제이다.

 

선택을 하지 않은 학생들 한 명씩 선택을 시작한다. 시작한 학생부터 한 명씩 선택을 하면서 동일한 그룹번호를 갖게 된다. 그러다가 선택을 했던 학생에게까지 가면 선택이 종료가 된다. 이후 마지막에 한 번 선택했던 학생이 다시 선택되었을 때 그 학생의 그룹번호와 시작 그룹번호가 같다면 사이클이 형성된 것이고, 다른 그룹번호의 학생을 선택했다면 다른 그룹을 선택하게 된 것으로, 사이클이 형성되지 않았음을 알 수 있다.

 

여기서 선택할 때에는 그룹번호를 갖고 있었지만, 사이클이 형성되어 팀이 결정된 학생들은 -1을 갖게 해주어서, 이후 팀이 없는 학생을 셀 수 있게 해주었다.

 

import sys

testcase = int(sys.stdin.readline())
for _ in range(testcase):
    n = int(sys.stdin.readline())
    choice = [0] + list(map(int, sys.stdin.readline().split()))
    visit = [0] * (n+1)

    group = 1
    for i in range(1, n+1):
        if visit[i] == 0:
            while visit[i] == 0:
                visit[i] = group
                i = choice[i]
            while visit[i] == group:
                visit[i] = -1
                i = choice[i]
            group += 1

    cnt = 0
    for v in visit:
        if v > 0:
            cnt += 1
    sys.stdout.write("{}\n".format(cnt))

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다