풀이
위상정렬(Topological sort) 문제
위상정렬은 작업간의 순서가 있어서 어떤 작업을 먼저 처리해야하는지 그 순서를 결정하는 문제
위상 정렬 문제 푸는 방법
1. 각 단계 별로 선행 과제의 갯수를 센다.
2. 선행과제가 없는 단계부터 처리하며 지워나간다.
3. 모든 단계를 처리한다.
크게 두 단계로 구성된다.
첫 번째는 사이클을 검사하는 단계이다.
이 단계에서는 텀 프로젝트의 접근법을 기반으로 하여 조금만 추가하였다.
사이클에서 제외된 인원의 수를 구하는 것에 추가적으로 사이클을 구성하는 인원의 수도 구해주었다.
두 번째는 검출한 사이클들을 바탕으로 DP를 수행하는 단계이다.
DP는 배낭 문제와 거의 동일하다.
사이클의 수가 i, 탑승가능 인원이 j라고 할 때 DP의 구성은 다음과 같다.
DP(i, j)는 i 번째 사이클까지를 이용하여 최대 j명 까지 탑승할 수 있을 때, 최대 탑승가능 인원
즉 사이클이 3개가 나왔다고 할 때, DP(2, 5)는 1,2번 사이클을 사용해서 5명 이하의 최대 탑승인원을 나타낸다.
DP(i, j)를 구하는 방법은 조건이 많이 때문에 그냥 코드로 보자.
w는 i번째 사이클의 인원이고, r은 i번째 사이클에서 제외된 인원을 나타낸다.
코드
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(' ')))
visit = [0] * (n+1)
cycle = []
notCycle = []
group = [0] * (n+1)
for i in range(1,n+1):
if visit[i] == 0:
dfs(i)
cycleCnt = len(cycle)
dp = [[0]*(n+1) for _ in range(cycleCnt+1)]
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)
