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

[백준 2668] 숫자고르기 Python 풀이

📌 문제 분석

이 문제는 결국 사이클을 찾는 문제입니다. 첫째 줄과 둘째 줄에서 고른 수들이 같아야 하는데, 이게 곧 사이클을 이루는 숫자들을 찾는 거랑 같습니다.

🚨 시행착오

처음에 DFS로 사이클을 찾으려고 했는데, 4%에서 자꾸 틀렸다고 나오더라구요.
한참을 고민하다가 사이클 판단하는 부분에 문제가 있다는 걸 발견했습니다!

처음 코드의 문제점

• 방문 체크랑 경로 추적을 제대로 안 해서 정확한 사이클을 못 찾고 있었습니다
• 현재 경로에 있는 노드들만 사이클로 봐야 하는데, 이전에 방문한 노드도 사이클로 잘못 판단했었죠
• 그러다 보니 사이클이 아닌 경우도 결과에 들어가는 문제가 생겼습니다

어떻게 고쳤나요?

• visited 집합으로 방문 체크하고
• path 리스트로 현재 경로를 추적하면서
• 현재 경로에서 시작점으로 돌아올 때만 사이클로 인정하도록 수정했습니다

💡 해결 방안

import sys

def dfs(start, current, visited, path):
    if current in visited:  # 이미 방문한 노드라면
        if current == start:  # 사이클이 완성된 경우
            result_set.update(path)  # 현재 경로의 모든 노드를 결과에 추가
        return

    visited.add(current)  # 현재 노드 방문 표시
    path.append(current)  # 현재 경로에 노드 추가
    dfs(start, numbers[current-1], visited, path)  # 다음 노드로 이동

N = int(sys.stdin.readline())
numbers = []
result_set = set()

for _ in range(N):
    numbers.append(int(sys.stdin.readline()))

# 각 노드에서 시작하여 사이클 찾기
for i in range(1, N+1):
    dfs(i, i, set(), [])

# 결과 출력
result = sorted(list(result_set))
print(len(result))
for num in result:
    print(num)

🎯 이 문제의 핵심 포인트

1. 모든 사이클을 찾아야 합니다: 작은 사이클, 큰 사이클 모두 찾아줘야 합니다
2. 방문 체크는 필수: 안 하면 무한루프 돌아요 😱
3. 경로 추적도 중요: 현재 경로에 있는 노드들만 사이클로 봐야 합니다
4. 중복 제거: set 쓰면 중복 걱정 없습니다!

📝 예제로 이해하기

N = 7
numbers = [3, 1, 1, 5, 5, 4, 6]

이런 입력이 들어오면:

• 1→3→1 (요건 사이클입니다!)
• 4→5→5 (이것도 사이클입니다!)
• 5→5 (자기 자신으로 돌아오는 것도 사이클입니다!)
• 2, 6, 7은 사이클이 아니니까 결과에 포함 안 됩니다

✨ 이번 문제를 통해 배운 점

1. 특수한 경우만 생각하다가는 함정에 빠질 수 있습니다
2. DFS 같은 그래프 탐색으로 깔끔하게 해결할 수 있습니다
3. 시행착오 겪으면서 더 좋은 방법을 찾게 됩니다

🔍 코드 설명

DFS로 사이클을 찾을 때 4가지 정보를 가지고 다녀요:

• 어디서 출발했는지 (start)
• 지금 어디 있는지 (current)
• 어디 어디 들렀는지 (visited)
• 여기까지 오면서 어떤 길로 왔는지 (path)

찾은 사이클은 result_set에 모아두고, 마지막에 정렬해서 예쁘게 출력하면 끝입니다!

이렇게 DFS를 활용하면 사이클을 효율적으로 찾을 수 있습니다 😊