백준 : 10451 (순열사이클) (DFS)

이번문제는 사이클 개수를 구하는 문제이다.

이는 DFS를 이용하여 자기자신이 나오면 사이클인것으로 간주하기로 했다.

 

여기서 주의할 점은 방문하지 않은 노드들을 기준으로 DFS를 거쳐 사이클 유무를 판단해야한다는거다.

방문한 노드들은 이미 전 사이클에 포함되는 노드이므로, 방문하지 않은 노드들에 대해서만 DFS(사이클 판별)를 거치도록한다.

 

1,3,5,7은 하나의 사이클이므로 첫 DFS에서 모두 방문 처리돼있다.

방문하지않은 2를 기준으로 DFS(사이클 판별) 한다.

방문하지 않은 4 ... (반복)

import java.util.*;

/*
 * 자기자신이 나오면 사이클 완성
 */

class Main {

	static int n, nodeCnt, start2, resultCnt;
	static boolean[] visited;
	static ArrayList<ArrayList<Integer>> graph;
	static int[] resultArr;

	public static void dfs(int now, int start) { // 초기값 고정을 위해 start사용
		visited[now] = true; // 방문표시

		for (int i = 0; i < graph.get(now).size(); i++) {
			int tmp = graph.get(now).get(i);

			if (tmp == start) { // 방문한 자기자신이 나오면 사이클 성공*****
				resultCnt++;
			}

			if (visited[tmp] == false) { // 아직방문전
				dfs(tmp, start); // 재귀
			}
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		n = sc.nextInt();
		resultArr = new int[n]; //초기화

		for (int k= 0; k < n; k++) { //횟수*****
			
			nodeCnt = sc.nextInt();

			// 초기화
			resultCnt =0; //출력 초기화 주의*****
			visited = new boolean[nodeCnt+1]; // 인덱스 0 사용안함*****
			graph = new ArrayList<ArrayList<Integer>>();
			for (int i = 0; i < nodeCnt + 1; i++) { // 인덱스 0 사용안함*****
				graph.add(new ArrayList<Integer>());
			}

			//그래프 입력
			for (int i = 1; i < nodeCnt + 1; i++) { // 인덱스 0 사용안함*****
				int a = sc.nextInt();

				graph.get(i).add(a); // 단방향*****
			}

			for (int i = 1; i < visited.length; i++) { // 방문안한 노드를 기준으로 사이클 판별, 인덱스 0 사용안함*****
				if (visited[i] == false) {
					dfs(i, i);
				}
			}
			
			resultArr[k] = resultCnt;
		}
		
		//출
		for(int result : resultArr) {
			System.out.println(result);
		}
	}

}