사이클
-
백준 2668 숫자고르기Algorithm/BOJ 2021. 6. 4. 23:05
출처: https://www.acmicpc.net/problem/2668 분류: 그래프, dfs 접근방식 1~n 까지에 각각 숫자가 매겨져 있을 때, 매겨진 숫자와 자신의 숫자의 집합이 같아지도록 최대한 많이 뽑아내는 문제입니다. 1~n을 노드 자신의 인덱스로, 매겨진 숫자를 다음 노드를 가리키는 그래프로 생각해보면, 결국 자기 자신으로 돌아오는 사이클이 아니면 절대 같은 집합이 될 수 없다는 걸 알 수 있습니다. 이렇게 각 사이클들을 더해주면 끝입니다 :) 전체 defaultVisit과 방문하면서 체크할 visit 배열을 만들어두고 탐색해서 사이클이 생겼다면 해당 visit을 defaultVisit으로 업데이트 시켜주는 방식으로 구현했습니다. for i in 0.. 0 { defaultVisit = v..