[BaekJoon] 백준 2668번 숫자고르기

[BaekJoon] 백준 2668번 숫자고르기

 

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

 

내코드

 

- 문제의 규칙을 찾아보면 다음과 같다.

- 사이클을 이루는 값이면 결과에 포함된다. 따라서 다음과 같이 풀었다.

- 1-N까지 반복을 돈다.

- 각 i번에 대해 i번에서 시작해서 dfs를 돌았을 때 이미 처음에 방문했던 i번으로 다시 돌아오게 된다면 사이클을 이루는 경우고 결과에 포함된다.

- 마지막에 sort를 해주지 않아 틀렸었다.

 

# BaekJoon2668.py

N = int(input())
arr = [[] for _ in range(N + 1)]
result = set([])
for i in range(N):
    tmp = int(input())
    arr[tmp].append(i + 1)

for i in range(1, N + 1):
    visited = [False for _ in range(N + 1)]
    stack = [i]
    visited[i] = True

    while stack:
        top = stack.pop()

        for j in arr[top]:
            if not visited[j]:
                stack.append(j)
                visited[j] = True
            elif visited[j] and i == j:
                result.add(j)

result = list(result)
result.sort()
print(len(result))
for i in range(len(result)):
    print(result[i])