[백준 2668번] 숫자고르기

2668번: 숫자고르기

n = int(input())

graph = [[] for _ in range(n+1)]
visited = [False]*(n+1)
temp = []

answer = set()

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

def dfs(index):
    global answer
    
    for i in graph[index]:
        if visited[i]:
            answer |= set(temp)
            return
        visited[i] = True
        temp.append(i)
        dfs(i)
        visited[i] = False
        temp.pop()
    
for i in range(1,n+1):
    dfs(i)

answer = sorted(list(answer))
print(len(answer))

for ans in answer:
    print(ans)

이번 문제는 선택한 첫째 줄의 원소의 집합과 두번째 줄의 원소의 집합이 일치하도록 할 때, 최대한 많이 선택할 수 있는 원소의 개수와 각 원소들을 구하는 문제이다.

 

처음에는 DFS과 백트래킹을 사용하여 해결하려고 했으나, 시간초과가 발생하였다.(100! 으로 인해 시간복잡도가 매우 큰 것으로 예상됨)

 

# Graph
1: [2, 3]
2: []
3: [1]
4: [6]
5: [4, 5]
6: [7]
7: []

다른 분들의 풀이를 참고해본 결과, 둘째 줄의 노드가 윗줄의 노드를 가리키고 있는 한 방향 그래프로 바꾸어 생각해보면 위와 같은 연결리스트와 그래프로 표현할 수 있다.

 

뽑을 수 있는 1, 3, 5 모두 사이클을 형성하는 것을 확인할 수 있다. 그렇다, 이 문제는 사이클을 찾아내어, 그것을 구성하는 노드를 모두 찾아내면 되는 문제였다.

 

즉, 인접한 노드를 확인할 때 이미 방문한 노드가 또 다시 등장한다는 것은 사이클이 존재한다는 것이다. 이렇게 사이클이 생기면 answer에 사이클을 구성하는 노드들을 모두 추가하고, 문제에서 요구하는대로 출력하면 된다.

 

배운 점 및 느낀 점

1. DFS와 백트래킹을 풀기전에 시간복잡도를 고려하자.
2. 감이 잘 오지 않는다면 문제에서 주어진 예시를 여러 자료구조로 생각해보고 특징을 찾아보자.