숫자 고르기

https://www.acmicpc.net/problem/2668

오답 풀이

https://github.com/KoJunHee/algorithm/blob/master/src/bj_2668/Main.java

완전 탐색으로 풀었다. 가능한 모든 경우를 조사하였다. 깊이 들어갈 때 마다, 두 집합이 일치하는지, 깊이는 몇인지 체크한다. 시간 초과가 났다. 모든 경우를 완전 탐색으로 찾으며 푸는것이 아니란 것이다.

정답 풀이

https://github.com/KoJunHee/algorithm/blob/master/src/bj_2668_02/Main.java

사이클 여부를 조사한다. 다음 이동할 지점이 시작점이면 사이클을 이룬 것이다. 문제에서 주어진 예시를 그림으로 그려보자.

1을 시작으로 dfs를 시작하자. 1 방문 체크를 한다. 다음 위치는 3이다. 3 방문 체크를 한다. 다음 위치는 1이다. 이미 방문한 곳이다. 시작점으로 돌아왔으니 싸이클을 이루었다. 시작점인 1을 리스트에 저장한다. 이번 dfs는 끝났다.

2를 시작으로 dfs를 시작하자. 2 방문 체크를 한다. 다음 위치는 1이다. 1 방문 체크를 한다. 다음 위치는 3이다. 3 방문 체크를 한다. 다음 위치는 1이다. 이미 방문한 곳이다. 이미 방문 한곳이 시작점이 아니기 때문에 사이클을 이루지 않는다. 이번 dfs는 끝났다.

이런 식으로 7을 시작으로 하는 dfs 까지 진행하고 리스트에 저장된 값을 출력한다.