BOJ 백준 파이썬 2668 숫자 고르기

문제의 조건인데

1:[3]

2:[1]

3:[1]

4:[5]

5:[5]

6:[4]

7:[6]

이것을 그래프로 그려보면

1,3,5는 사이클을 이룸을 알 수 있다.

사이클을 이루는 원소들을 찾아내는 것이 문제 풀이 방법이란 것을 알 수 있다.

방향 그래프란 것도 낯설었고 문제의 조건을 보자마자 그래프를 이용한 사이클 문제라는 것을

떠올리는 것도 아직은 쉽지 않아 보인다.

문제 풀이 경험을 더 해야한다.

사이클을 찾는 방법은 기본적으로 dfs 탐색으로 각 정점을 방문하다가

이미 방문했던 정점을 또 방문하면 사이클을 형성하는 것이다.

16932 모양 만들기와 똑같은 문제다.

 

import sys
from collections import deque
from itertools import combinations
 
 
def dfs(x):
    if ch[x]==1:
        if x in cycle:
            for num in cycle[cycle.index(x):]:
                res.add(num) 
    else:
        ch[x]=1
        cycle.append(x)
        y=graph[x]
        dfs(y)
               
 
if __name__=='__main__':
    sys.stdin=open("input2.txt", "rt")
    
   
 
    n=int(input())
 
    graph=[]
 
    for _ in range(n):
        x=int(input())
        x-=1
        graph.append(x)
 
    ch=[-1]*n 
 
   
    
    res=set()
    for i in range(0,n):
        if ch[i]==-1:
            cycle=[]
            dfs(i)
    res=list(res) 
    res.sort()
    print(len(res))
    for x in res: 
        print(x+1)