[백준 - Python] 2668 - 숫자 고르기

0.  문제 링크

 

 

https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

---

1.  풀이 방법

 

해당 문제는 단순히 사이클이 존재하는 노드를 집합으로 넣으면 되는 문제이다.

나는 전혀 최적화를 하지 않고, 모든 노드를 살펴보면서 탐색하게 하였다.

물론 이 방법이 좋은 것은 아니지만, 그래도 꽤 시간은 빨랐다.

아무튼 DFS를 하다가 특정 노드가 이미 True로 설정되어 있다면, 이는 사이클이 생긴 것이므로 이를 ans set에 넣고 반환하게 하였다.

---

2.  코드

 

 

def dfs(start):
    if visited[start]:        # 싸이클이 생김
        ans.add(start)
        return
    else:
        visited[start] = True
        dfs(adj[start])
        visited[start] = False


if __name__ == "__main__":
    n = int(input())
    ori = list(range(1, n + 1))
    lst = [int(input()) for _ in range(n)]
    visited = [False] * (n + 1)
    ans = set()     # 정답 세트
    adj = dict()        # 인접리스트

    for i in range(n):
        adj[i + 1] = lst[i]     # 인접리스트를 만듬

    for i in range(1, n + 1):
        dfs(i)      # 1부터 차레대로 사이클을 찾음

    print(len(ans))
    print(*sorted(list(ans)), sep='\n')

---

3.  마무리

 

 

아무 생각 없이 문제 풀었는데, 맞아서 몹시 당황했다.