[백준] 2668. 숫자고르기 (Python)

백준 2668번 문제, 숫자고르기

2668번: 숫자고르기

골드 5

---

문제 

세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절히 뽑으면, 그 뽑힌 정수들이 이루는 집합과, 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다. 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오. 예를 들어, N=7인 경우 아래와 같이 표가 주어졌다고 하자.

이 경우에는 첫째 줄에서 1, 3, 5를 뽑는 것이 답이다. 첫째 줄의 1, 3, 5밑에는 각각 3, 1, 5가 있으며 두 집합은 일치한다. 이때 집합의 크기는 3이다. 만약 첫째 줄에서 1과 3을 뽑으면, 이들 바로 밑에는 정수 3과 1이 있으므로 두 집합이 일치한다. 그러나, 이 경우에 뽑힌 정수의 개수는 최대가 아니므로 답이 될 수 없다.

---

입력

 

첫째 줄에는 N(1≤N≤100)을 나타내는 정수 하나가 주어진다. 그 다음 줄부터는 표의 둘째 줄에 들어가는 정수들이 순서대로 한 줄에 하나씩 입력된다.

 

출력

첫째 줄에 뽑힌 정수들의 개수를 출력하고, 그 다음 줄부터는 뽑힌 정수들을 작은 수부터 큰 수의 순서로 한 줄에 하나씩 출력한다.

 

예제 입력 1

7
3
1
1
5
5
4
6

 

 

예제 출력 1

3
1
3
5

---

=> 위에서 뽑힌 수의 집합과 그 수들의 짝꿍수 집합이 동일해야한다!

 

직접 그림을 그려봐야 풀기 쉬운 문제.

 

이걸 하나씩 따라가보면,

위와 같은 그림이 그려진다.

 

여기서 싸이클이 생기는 부분만 체크해보면,

 

사이클에 포함된 수([1, 3, 5])가 정답([1, 3, 5])이 된다는 것을 알 수 있다.

 

고로, 각 번호마다 탐색하면서,

사이클이 발생할 경우, 사이클에 포함된 수를 모두 결과 배열에 넣어준다. (중복없이)

이후, 결과 배열을 정렬하고 출력해주면 정답

 

 

cycle_check 함수를 만들어 사이클을 체크해주고,

사이클이 발생할 경우 사이클에 포함된 모든 수를 결과배열에 넣도록 했다.

 

제출한 코드는 아래와 같다.

def cycle_check(num, visited):
    global result
    to_visit = list()
    to_visit.extend(same_list[num])

    while to_visit:
        n = to_visit.pop()
        if n not in visited:
            visited.append(n)
            cycle_check(n, visited)
            visited.pop()

        else:
            idx = visited.index(n)
            for v in visited[idx:]:
                if v not in result:
                    result.append(v)

            return


if __name__ == "__main__":
    N = int(input())

    same_list = [[] for i in range(N+1)]

    for i in range(1, N+1):
        n = int(input())
        same_list[n].append(i)  

    result = list()
    for i in range(N+1):
        cycle_check(i, [])

    result.sort()
    print(len(result))
    for r in result:
        print(r)