백준 - 2668 숫자고르기

이 문제는 사이클을 찾는 문제이다.

사이클이라는 것은 결국 시작점에서 탐색을 끝마치는 노드가 다시 시작점이 되어야 한다는 것이다.

다른 사람들의 코드를 참고하면서 인사이트를 얻게 되었다.

from collections import defaultdict

def dfs(start, path):
    path.add(start)
    visit[start] = 1

    for i in dic[start]:
        if i not in path:
            dfs(i, path.copy())
        else:
            result.extend(list(path))
            return

n = int(input())
dic = defaultdict(list)
result = []

for i in range(1,n+1):
    dic[int(input())].append(i)

visit = [0] * (n+1)

for i in range(1, n+1):
    if not visit[i]:
        dfs(i, set([]))

print(len(result))
result.sort()

for i in result:
    print(i)

---

1. defaultdict

이것은 값이 없을 때, 기본값을 설정하는 것이다. 위의 코드에서 알아본다면,

dic = defaultdict(list)

for i in range(1,n+1):
    dic[int(input())].append(i)

dic가 입력받는 값을 key로 가지고 있지 않다면 위에서 지정한 비어있는 list를 갖게 된다.

예를 들어, dic[1] = []가 되는 것이다.

2. 사이클의 정의

해당 문제에서 dic 형태로 입력을 받게 된다면, 그것을 출력했을 때 아래와 같이 나온다.

defaultdict(<class 'list'>, {3: [1], 1: [2, 3], 5: [4, 5], 4: [6], 6: [7]})

이것은 결국 연결 되어있는 노드들만 나타낸 것이다. 이러한 점을 이용해서 하나씩 가져올 때, 방문처리가 되어있다면 그것은 사이클을 형성하고 있다는 것이다.

for i in dic[start]:
        if i not in path:
            dfs(i, path.copy())
        else:
            result.extend(list(path))
            return

이 부분에서 i의 else문에서 사이클 형성 시 그것을 구성하는 노드를 리스트에 저장한다.