[백준] 2668 숫자고르기

문제

• Nx2 크기의 표가 있다.
• 첫째 줄의 각 칸에는 정수 1~N이 차례로 들어 있고, 둘째 줄의 칸에는 1이상 N이하인 정수가 들어있다.
• 첫째 줄에서 숫자를 적절히 뽑으면 그 뽑힌 정수들이 이루는 집합과 뽑힌 정수들의 바로 밑의 둘째 줄에 들어있는 정수들이 이루는 집합이 일치한다.
• 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법 찾기
• 1 <= N <= 100

 

풀이

• 둘째 줄 -> 첫째 줄의 관계로 그래프로 표현할 수 있다.
• 예를 들어 예제에서는 다음과 같이 표현할 수 있다.

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

 

• 구하고자 하는 것은 "사이클이 존재하는" 그래프의 노드의 최대 집합이다.
  • 사이클이 존재한다 = 방문했던 노드에 다시 방문한다.

 

 

 

from collections import defaultdict
import sys
sys.setrecursionlimit(10**4)

def dfs(now, visited) :
    visited.add(now)
    checked[now] = True

    for nxt in graph[now] :
        # 사이클이 아닌 경우
        if nxt not in visited :
            dfs(nxt, visited.copy())
        # 사이클이 생긴 경우
        else :
            answer.extend(list(visited))
            return


N = int(input())
graph = [[] for _ in range(N+1)]
for i in range(1, N+1) :
    num = int(input())
    graph[num].append(i)

checked = [False] * (N+1)	# 숫자 확인
answer = []        		# 정답 리스트
for i in range(1, N+1) :
    if not checked[i] :		# 확인하지 않은 숫자에 대해서만 확인할 것
        dfs(i, set())

print(len(answer))
print(*sorted(answer), sep='\n')

 

References

• 백준 그래프탐색