[백준] 10451번 : 순열 싸이클 자바(JAVA) 풀이

문제

---

---

문제 탐색하기

문제를 읽고나서 이 부분들이 이해가 잘 가지 않았다. 알고 봤더니 

위와 같이 사이클이 만들어지는 것이었다.

• 사이클이 만들어지는 경우
  • 어떤 정점에서 출발해 이어진 경로를 타고 탐색하다가 그 정점으로 돌아오는 경우 

이 과정을 DFS로 구현할 수 있다.

1. 방문하지 않은 노드일 경우
   
   • 새로운 순환 사이클로 그 정점으로부터 탐색을 시작하고, 탐색 과정에서 발견된 사이클에 포함된 노드들을 TRUE로 변경해준다.
   • 사이클을 카운트 해준다.

가능한 시간복잡도

입력 범위 ( 2 ≤ N ≤ 1,000)

최대 정점 N개에 대해 탐색을 진행한다. 사이클을 확인하는 과정에서 간선 탐색을 진행하게 되는데, 한 번 방문한 간선을 다시 방문하지 않으므로(선형탐색) 시간 복잡도는 O(N) 이 된다.

 

---

코드 설계하기

• graph 배열을 만들어 주어진 순열을 배열에 저장한다.
• visited 배열을 만들어 방문 여부를 체크해준다. (기본값 False)
• 방문하지 않은 노드일 경우

• 방문 처리
• 해당 노드가 가리키는 노드가 방문처리 되어있는지 체크
• 방문 처리 X → 경로 타고 탐색
• 방문 처리 O →사이클이 있는 것이므로 탐색 종료 
• 순환 사이클 카운드 +1

---

풀이 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	// 방문처리에 사용할 배열 선언
	static boolean[] visited;
	// 그래프 담는 배열 선언 
	static int[] graph;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int testcase = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		int cycle = 0; // 순열 사이클 카운트할 변수 선언
		
		for(int i=0;i<testcase;i++) {
			int n = Integer.parseInt(br.readLine());
			visited = new boolean[n+1];
			graph = new int[n+1];
			cycle = 0;
			
			st = new StringTokenizer(br.readLine());
			for(int j=1;j<n+1;j++) {
				// 주어진 순열 배열에 저장
				graph[j] = Integer.parseInt(st.nextToken());
			}
			
			for(int j=1;j<n+1;j++) {
				if(!visited[j]) { // 방문하지 않았으면 
					dfs(j);
					cycle++;
				}
			}
			System.out.println(cycle);
		}
		
	}
	
	// 재귀 형태로 구현 함수
	static void dfs(int start) {
		// 방문 처리 
		visited[start] = true;
		
		int next = graph[start];
		if(!visited[next]) { // 방문하지 않았다면
			dfs(next);
		}
		
	}
}