[백준 알고리즘][DFS] 10265번 MT

문제

남규는 동기들과 엠티를 가기 위해 버스를 대절했다. 그런데 과사의 실수로 대절버스의 인원이 잘못되어 남규의 동기들을 모두 태울 수 없었다. 이 와중에 동기들은 화를 내며 다음과 같은 말들을 주고받았다.

재혁: 동우가 안 가면 나도 안 간다.
동우: 세종이가 안 가면 난 안 갈래.

버스에 태울 수 있는 인원수는 한정되어 있는데 모두들 다른 누군가가 가지 않으면 자신도 가지 않겠다 하니 남규는 신경이 뻗쳤다. 게다가 술을 너무 많이 샀기 때문에 최대한 많은 인원을 데려가지 않으면 안 되는 상황이었다.

각 사람이 원하는 같이 갈 사람이 주어질 때, 버스에 태울 수 있는 사람은 최대 몇 명인지 알아내시오.

입력과 출력

첫 번째 줄에 사람 수 n과 버스에 태울 수 있는 사람 수 k가 주어진다. (1 ≤ k ≤ n ≤ 1 000)

두 번째 줄에 n개의 정수 xi (i = 1, 2, ... , n, 1 ≤ xi ≤ n) 가 순서대로 주어진다. xi는 xi번째 사람이 버스에 타지 않는다면 i번째 사람 역시 버스에 타지 않음을 의미한다. 

결과는 모든 사람의 의견을 해치지 않고 최대한 태울 수 있는 인원수를 출력한다.

풀이

싸이클..?이라해야하나 사이클찾기 맞는거같다 2->3->2가 되면 2, 3 둘 다 태울 수 있고 그때 포함되는 사람이 2명이니까 그 때 태울 수 있는 명수보다 작으면 태운다 이미 누군가 타있는데 원래 태울 수 있는 인원보다는 작지만 기존에 먼저 태운사람들때문에 못타면 그 사람들을 빼고 태운다! 이부분이..어려울거같지만

테스트 케이스는 다 맞았는데 틀렸습니다가 나온다....질문검색을 보니까 내가 생각한 앞부분+ DP로 풀어야하는거 같은데....

예외케이스를 못찾으니 해결을 못하겠다 ㅠㅠ