2668_숫자고르기

입력

첫째 줄에 리스트의 길이 입력
두째 줄부터 N+1 줄까지 key에 대한 value 입력

출력

key1 == key2_value && key2 == key1_value 조건을 만족하면서
첫 번째 줄에서 뽑은 집합과 두 번째 줄에서 뽑은 집합의 최대 길이와 요소들을 출력

조건

• ex) 1-3 / 3-1 과 같이 서로 사이클을 이룬다는 조건을 만족해야 함
• 최종 집합의 요소들을 출력할 때 오름차순 정렬

풀이

사이클이 발생하는 모든 요소들을 체크하는 풀이 -> 깊이 우선 탐색

1. N개의 key를 가지는 딕셔너리와 방문 체크를 위한 visited 리스트 생성

key	해당 key값을 value로 받는 key 리스트
1	2, 3
2
3	1
4	6
5	4, 5
6	7
7

N = int(input())
my_input = {key:[] for key in range(1, N+1)}
ans = set()

for key in range(1, N+1): my_input[key].append(int(input()))

2. 1부터 N까지의 key값을 돌며 사이클이 존재하는 경우를 찾기 위해 깊이 우선 탐색
   하나의 key값을 돌 때마다 방문 체크(visited)를 초기화 시켜줘야 사이클을 확인할 수 있음
   사이클이 존재하는 경우 ans에 추가하고 해당 key 방문 체크

def dfs(key, visited):

    visited[key] = 1

    for elem in my_input[key]:
        if visited[elem] == 0: dfs(elem, visited)
        else:
            if elem not in ans:
                ans.add(key)
                ans.add(elem)
                visited[elem] = 1

for key in range(1, N+1):
    visited = [0]*(N+1)
    dfs(key, visited)

3. ans를 리스트로 형변환하고 오름차순 정렬 후 출력

ans = list(ans)
ans.sort()
print(len(ans))
for ans_ in ans: print(ans_)

전체 코드

숫자고르기