BOJ-2668-숫자고르기

BOJ 2668 숫자고르기

문제출저

풀이

int형 배열을 숫자들을 담는 자료구조로 이용하였다.
첫번째수는 int형 배열의 idx값이 되고, 두번째 nums[idx]의 값으로 담았다.

숫자를 뽑는 방법은 2가지 경우가 존재

1. 첫째줄과 두번째가 같은수일 경우
   idx == nums[idx]

2. 첫째줄의 수(idx)로 시작해서 두번째줄의 수(nums[idx])가 idx로 끝나는 경우(사이클이 형성되는 경우, 아래그림 참조)

   

1부터 N까지 1,2의 경우를 체크해주면 되는데, 2의 경우 DFS를 이용하여 사이클을 형성되는지 확인할 수 있다.
dfs 함수의 매개변수로는 int startIdx, int curIdx, boolean[] chk가 되는데,
startIdx값이 탐색을 시작하는 초기 인덱스값이 되고, curIdx은 현재 탐색 인덱스 값이 된다.
chk배열은 한번 방문한 정점이 또 다시 방문되는것을 방지하기 위해 사용된다.

위의 그림에서 시작인덱스가 1일 경우 dfs함수는 dfs(1, 3(nums[1]), chk)로 호출될것이다.

소스코드

전체소스

사이클을 확인하기 위한 dfs 함수

public void dfs(int stIdx, int idx, boolean[] chk) {
		if (stIdx == idx) {
			// 사이클 존재
		}

		if (!chk[idx]) {
			chk[idx] = true;
			dfs(stIdx, nums[idx], chk);
		}

	}