9466. 텀 프로젝트 (Python)

9466번: 텀 프로젝트

 

풀이

 각 학생마다 dfs를 돌려서 해결할 수 있는 문제이다. 학생의 상태를 기록해 놓는 teamFlags 리스트를 하나 만들어둔다. teamFlags 리스트의 값은 0일 경우는 아직 탐색하지 않은 상태, 1일 경우는 팀을 이룬 학생, -n일 경우는 팀을 이루지 못한 학생임을 의미한다. n은 dfs 함수가 실행될 때마다 1씩 증가한다. 

 

 아직 탐색하지 않은 학생일 경우 dfs 탐색을 진행해가며 teamFlags[학생번호]에 -n을 설정한다. 탐색 과정에서 -n을 만나게 되면 팀을 설정하는 함수를 실행시킨다.

 문제의 예제에서 4번 학생에서 dfs를 하면 4 -> 7 -> 6 -> 4가 되고 마지막 4에서 -n을 만나게 된다. 그럼 이제 4부터 -n의 값을 만날 때까지 teamFlags의 값을 1로 설정해준다. 

 1번 학생의 경우 1 -> 3 -> 3이 되고 마지막 3에서 -n을 만나게 된다. 3부터 -n의 값을 만날때 까지 teamFlags의 값을 1로 설정하면 teamFlags[1]의 경우는 그대로 -1이 되고 teamFlags[3]의 경우는 1로 설정되어 1번 학생을 팀을 이루지 못하고 3번 학생의 경우 팀을 이루는 것으로 설정된다. 

 

 탐색을 다 마친 후 마지막에 전체 학생에서 팀을 이룬 학생의 수를 뺀 값을 출력해 주면 된다.

 

코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)

# 사이클을 이룬 학생들끼리 팀을 설정


def makeTeam(sNum, flagNum):
    global teamStudents

    while teamFlags[sNum] == flagNum:  # 현재 dfs 탐색에 속해 있는 학생들에 한해서
        teamFlags[sNum] = 1  # 팀을 이룬 학생임을 표시하고
        sNum = pickNumbers[sNum]  # 다음 학생을 가져오고
        teamStudents += 1  # 팀을 이룬 학생의 수를 증가시킨다


# 팀을 이룰 수 있는지 체크하기 위한 dfs 탐색
def checkTeam(sNum, flagNum):  # sNum: 현재 학생 번호
    if teamFlags[sNum] == flagNum:  # flagNum을 만나면 dfs 탐색 중에 사이클이 있음을 의미한다.
        makeTeam(pickNumbers[sNum], flagNum)  # 사이클을 형성하는 학생들끼리 팀을 이루도록 함수 호출
        return
    elif teamFlags[sNum] == 0:  # 아직 탐색하지 않은 학생이라면
        teamFlags[sNum] = flagNum  # flagNum으로 일단 값을 설정해주고
        checkTeam(pickNumbers[sNum], flagNum)  # 다음 학생으로 탐색을 계속한다.
    else:  # 이미 팀을 이룬 학생이거나 이전 dfs 탐색에서 살펴봤던 학생일 경우 추가 작업 없이 종료
        return


if __name__ == '__main__':
    T = int(input())
    for _ in range(T):
        N = int(input())
        pickNumbers = list(map(int, input().split()))
        pickNumbers.insert(0, -1)

        # -n: 팀을 이루지 못한 학생, 1: 팀을 이룬 학생, 0: 아직 결정되지 않은 학생
        teamFlags = [0 for _ in range(N+1)]
        flagNum = -1  # dfs가 진행될때마다 1씩 감소한다
        teamStudents = 0  # 팀을 이룬 학생의 수

        for i in range(1, N+1):
            if teamFlags[i] == 0:
                checkTeam(i, flagNum)
                flagNum -= 1  # 한 번 dfs가 진행되고나면 flagNum을 1 감소시킨다.

        print(N - teamStudents)  # 전체 학생 - 팀을 이룬 학생의 수