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

2668번: 숫자고르기

2668번: 숫자고르기

🤔 문제분석

깊이 우선탐색으로 아래 숫자를 뽑아서 그 숫자로 이동하면서, 위쪽 집합과 아래쪽 집합이 동일할 경우 정답 리스트에 값을 추가시켜줍니다. 위쪽 집합과 아래쪽 집합이 같다는건 결국 집합을 만들 수 있다는 조건을 만족시키기 때문입니다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())
nums = [int(input()) for _ in range(N)]

def dfs(idx):
    if visited[idx] == False:
        visited[idx] = True
        
        top.add(idx+1)
        bottom.add(nums[idx])
        
        if top == bottom:
            ans.extend(list(top))
            return
        
        dfs(nums[idx]-1)
        
    visited[idx] = False

ans = []
for i in range(N):
    visited = [False for _ in range(N)]
    top = set()
    bottom = set()
    dfs(i)
    
ans = list(set(ans))
ans.sort()

print(len(ans))

for n in ans:
    print(n)

🎯 피드백 및 개선사항

Top 과 Bottom을 나누어서 Top과 Bottom이 같을경우 정답리스트에 추가해 가는 풀이 방법이 있었고, 자기자신을 시작으로 사이클이 발생하는 여부를 체크하여 정답리스트에 추가하는 방식이 있습니다. 첫번째 풀이 방법이 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치 한다는 조건을 잘 만족시키는 것 같아서 해당 풀이를 참조하게되었습니다.