숫자고르기1 [백준]BOJ 2668: 숫자고르기 - C++/DFS 2668번: 숫자고르기 (acmicpc.net) 문제풀이문제를 간단하게 표현하면 그래프 내의 사이클을 모두 찾은 다음에, 사이클에 포함되는 노드을 모두 출력하면 된다. 사이클을 찾으려면 그래프내의 모든 노드에서 dfs를 쓰면 되는데 다음과 같은 케이스들로 나눌 수 있겠다. 1. 사이클에 도달하긴 하나 시작 노드는 사이클에 포함되지 않는 케이스 주어진 예제에서 2번, 4번, 6번, 7번 노드가 해당한다.탐색을 시작한 노드에서 사이클에 도달하긴 하나, 시작한 노드는 사이클에 포함되지 않는다. 최적화를 위해 이러한 케이스에도 사이클만 따로 분리해 중복되는 연산을 줄일 수 있겠지만, 이 문제의 n이 큰 수가 아니므로, 그냥 아무런 행동도 하지 않는다. 2. 탐색을 시작한 노드가 사이클에 포함되는 케이스예제에서 .. 2024. 6. 4. 이전 1 다음
