[백준] 2668. 숫자 고르기 (Python)

📌 2668. 숫자 고르기

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

풀이과정

아이디어를 생각은 했지만, 그것을 코드로 구현하는 것이 어려웠다. 밑에 배열을 down이라고 하면, 인덱스가 주어지면, down[인덱스]를 확인하고 first, second에 각각 넣은 후 first와 second가 같은 지 확인한다. 같다면 return 하고 같지 않다면 down[인덱스]를 인덱스라고 가정하고 다시 반복한다. 여기까지는 얼추 생각을 했는데, 언제 이 반복을 break 해야하는지에 대한 아이디어가 부족했다. 찾아 본 결과, first에 down[인덱스]가 있지만 first와 second가 다른 경우 break을 해주면 된다.

풀이법을 살펴보니 이 과정은 사이클을 찾는 과정이었다. 흠 사이클 찾는 과정하면 크루스칼 알고리즘인데.

여기서 visited의 역할은 for i not in answer로 대신하는 듯하다. 조금 더 시간을 줄이고 싶다면 visited를 써서 한번 dfs돌려진 것은 pass하도록 하면 될 것이다.

💯 정답

n = int(input())

#up = [i+1 for i in range(n)]
down = [0]
for i in range(n):
  down.append(int(input()))

first = []
second = []
answer = set()

def dfs(idx, first, second):
  first.add(idx)
  #print(idx)
  second.add(down[idx])
  if down[idx] in first:
    if first == second:
      #print(answer)
      answer.update(first)
    return
  return dfs(down[idx], first, second)

for i in range(n):
  if i+1 not in answer:
    dfs(i+1, set(), set())

print(len(answer))
answer = list(answer)
answer.sort()
for data in answer:
  print(data)

✍ 끄적끄적

몰라서 풀이법을 찾아보다가 해설에

골드5 치고는 너무 쉬운 문제

이렇게 적혀있는 것을 보고 머리가 뎅 했다.