알고리즘 - 순열 사이클

문제

• 링크

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	
	static BufferedReader br;
	static BufferedWriter bw;
	static int T, N, answer;
	static ArrayList[] arr;
	static int[] visited;
	public static void main(String[] args) throws IOException{
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		T= Integer.parseInt(br.readLine());
		for(int i = 0; i < T; i++) {
			answer = 0;
			N = Integer.parseInt(br.readLine());
			StringTokenizer stk = new StringTokenizer(br.readLine());
			arr = new ArrayList[N+1];
			for(int j = 1; j <= N ;j++) {
				arr[j] = new ArrayList();
				arr[j].add(Integer.parseInt(stk.nextToken()));
			}
			
			visited = new int[N+1];
			for(int j = 1; j <= N ; j++) {
				if(visited[j] == 0) {
					answer++;
					bfs(j);					
				}
			}
			bw.write(answer+"\n");
		}
		bw.flush();
		bw.close();
		
		
	}
	private static void bfs(int j) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(j);
		visited[j] = 1;
		while(!queue.isEmpty()) {
			int poll = queue.poll();
			
			for(int i = 1; i <=N ;i++) {
				if(visited[i]==0 && arr[poll].contains(i)) {
					visited[i]=1;
					queue.offer(i);
				}
			}
			
		}
		
		
	}
}

회고

• 기본적인 DFS, BFS, 인접 행렬, 인접 리스트 활용은 할 줄 알아야 한다
• 책과 반복적인 풀이를 통해 하나씩 풀어나가자