(DFS) 10265번 MT

def dfs(v):
    cycleMember = [v]
    visit[v] = 1
    group[v] = len(cycle)
    while True:
        if group[choice[v]] == -1:
            group[choice[v]] = group[v]
        else:
            group[v] = group[choice[v]]

        v = choice[v]
        if visit[v] == 0:
            visit[v] = 1
            cycleMember.append(v)
        else:
            if v in cycleMember:
                cycleStartIdx = cycleMember.index(v)
                cycle.append(len(cycleMember) - cycleStartIdx)
                notCycle.append(cycleStartIdx)
                return
            else:
                notCycle[group[v]]+=len(cycleMember)
                return

n, k = map(int, input().split(' '))
choice = [0] + list(map(int, input().split(' '))) # 1번 학생부터 지명한 학생을 담기 위한 리스트 생성

visit = [0] * (n+1) # 방문 경로를 기록할 visit 리스트 생성

# 순환 함수가 되는 경우 순환 함수의 해당하는 학생들이 전부 mt를 갈 수 있거나
# 전부 mt를 갈 수 없다. 이를 체크해주기 위해 2개의 리스트를 만들어준다.
cycle = [] 
notCycle = []

group = [0] * (n+1)

# 1부터 검사
for i in range(1,n+1): # 순환 함수 체크
    if visit[i] == 0: # 아직 방문하지 않았으면
        dfs(i) # dfs 방문처리
cycleCnt = len(cycle)

dp = [[0]*(n+1) for _ in range(cycleCnt+1)] # dp 메모리얼 리스트 생성

for i in range(1, cycleCnt+1):
    w = cycle[i-1]
    r = notCycle[i-1]
    for j in range(1,n+1):
        if w <= j:
            dp[i][j] = w
            if w+r >= j:
                dp[i][j] = j
            if dp[i-1][j-w] >= 0:
                dp[i][j] = max(dp[i-1][j-w]+w, dp[i-1][j], dp[i][j])
            else:
                dp[i][j] = max(dp[i][j], dp[i-1][j])
        else:
            dp[i][j] = max(dp[i][j], dp[i-1][j])
ans = 0
for i in range(1,n+1):
    if dp[cycleCnt][i] >= 0 and dp[cycleCnt][i] <= k:
        ans = max(ans, dp[cycleCnt][i])

print(ans)

참고할 블로그

문제의 아이디어는 학생들은 자기가 지목한 학생이 안갈경우 자신도 안가게 되니깐 학생들 사이에 순환(사이클)이 생기게 된다. 순환이 생길경우 학생들은 전부 가거나 전부 못 가는 경우가 생긴다.

순환이 생겼는데 갈 수 있는 학생 수보다 순환이 클 경우 -> 전부 못간다.
만약에 6번 학생과 7번 학생이 순환이 생겼는데 8번 학생이 6번 학생이 안가면 자신도 안간다고 할 경우 6번 7번 학생을 보내고 8번 학생을 안보내면 된다.