[BOJ2668] 숫자고르기

숫자 최대한 많이 뽑기

• 세로 두 줄, 가로 N개 칸으로 이루어진 표
• 첫째 줄 : 1, 2, …, N
• 둘째 줄 : 각 칸에 1이상 N이하 정수
• 숫자 적절히 뽑으면, 뽑힌 정수들의 집합과, 뽑힌 정수 바로 밑의 (둘째 줄) 정수들이 이루는 집합이 일치
• 위 조건에 일치하는 정수 최대 개수

입력

• 첫째 줄 N (1 <= <=100)
• 둘째 줄에 들어가는 정수 순서대로

출력

• 첫째 줄에 뽑힌 정수들의 개수 출력
• 뽑힌 정수들을 작은 수부터 큰 수 순서로

설계

• DFS 이용
• Graph는 ‘첫째 줄 인덱스와 둘째 줄 값, 둘째 줄 값에 해당하는 첫째 줄 인덱스와 둘째 줄 값’ 과 같은 방식으로 구성
• 여기서 start node 와 current node가 같아지는 순간이 문제의 조건에 해당
• N번 반복 -> dfs의 시작 노드 (1 ~ N) (반복마다 방문 변수 초기화)
• 해당 조건의 start node를 배열에 넣어 출력

How I solved(click to github)

---

ref :
BOJ2668