[백준] 10451 : 순열 사이클 JAVA 풀이

 

입력받는 방식을 제외하면

연결 요소의 개수를 세는 문제와 풀이가 같은 문제였다.

 

import java.io.*;
import java.util.*;
public class Main {
	static int[][] graph;
	static boolean[] visit;
	static int N;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		// 테스트케이스의 개수를 입력받음
		int T = Integer.parseInt(br.readLine());
		
		// 테스트케이스의 개수만큼 반복
		for(int i=0;i<T;i++) {
			// 한 테스트케이스의 정점의 수를 입력받음
			N = Integer.parseInt(br.readLine());
			
			// 그래프와 정점을 방문했는지 확인할 행렬 생성
			graph = new int[N+1][N+1];
			visit = new boolean[N+1];
			
			// N개의 정점을 저장할 어레이리스트 생성
			ArrayList<Integer> V = new ArrayList<>();
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
            // 입력받은 정점을 리스트에 추가
			for(int j=0;j<N;j++) {
				V.add(Integer.parseInt(st.nextToken()));
			}
			
			// 입력받은 정점들로 그래프를 생성함
			makeGraph(V);
			
			// 사이클의 개수를 카운트하는 변수
			int cnt = 0;
			
			// N개의 정점에 대해 아직 방문하지 않았다면 bfs를 수행하고 cnt증가시킴
			for(int k=1;k<=N;k++) {
				if(visit[k]==false) {
					bfs(k);
					cnt++;
				}
			}
			// 사이클의 개수 출력			
			System.out.println(cnt);
		}
	}
	
    // 그래프를 만드는 메서드
	public static void makeGraph(ArrayList<Integer> V) {
		for(int i=1;i<=V.size();i++) {
			graph[i][V.get(i-1)] = 1;
		}
	}

	// BFS
	public static void bfs(int v) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(v);
		visit[v] = true;
		
		while(!q.isEmpty()) {
			int tmp = q.poll();
			
			for(int i=1;i<=N;i++) {
				if(graph[tmp][i]==1&&visit[i]==false) {
					q.offer(i);
					visit[i] = true;
				}
			}
		}
	}

}