10451번

https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

이번 문제는 순열 사이클의 갯수를 찾는 문제였다. 그런데 이 문제는 11724번과 로직이 똑같았다.

BFS로 탐색을 진행하면서 탐색이 끝날때마다 카운트를 세면 되는 로직이었다.

 

가장 기본적인 BFS라고 생각할 수 있다.

그래서 오늘은 BFS에 대해서 간단하게 정리해보려고 한다.

 

BFS란 한국말로 너비우선탐색이다.

너비를 우선 탐색한다는게 무슨뜻인가? 말그대로 시작노드에서 그에 인접한 노드들을 탐색하고,

그 다음 인접 노드들을 탐색하면서 물방울이 물웅덩이에 떨어지면 퍼지는 것처럼 탐색하는 방법이라고 이미지를 생각하면 된다.

 

그래서 BFS는 DFS(깊이 우선 탐색)과 다르게 Queue를 사용한다.

 

Queue에 인접한 노드들을 넣고, 하나씩 꺼내면서 꺼낸 노드에 인접한 노드들을 확인하는 방식이다.

그래서 DFS와는 다르게 항상 최단거리, 최소값을 구할 수 있다.

 

하지만 이 문제에서는 값과는 상관없이 방문처리로 사이클을 찾고, 사이클을 찾은 횟수를 기록하는 문제이다.

 

그래서 정답코드는 아래와 같다.

package backjoon.b10451;

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

public class b10451 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int step = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<step; i++){
            int N = Integer.parseInt(br.readLine());
            Graph g = new Graph(N);
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++){
                g.addEdge(j,Integer.parseInt(st.nextToken()));
            }
            int count = 0;
            for(int j=1; j<=N; j++){
                if(!g.visit[j]) {
                    g.bfs(j);
                    count++;
                }
            }
            sb.append(count).append("\n");
        }
        System.out.println(sb);
    }
}
class Graph{
    LinkedList<Integer>[] adj;
    boolean[] visit;

    Queue<Integer> queue;
    public Graph(int N) {
        adj = new LinkedList[N+1];
        visit = new boolean[N+1];
        for(int i=0; i<=N; i++){
            adj[i]=new LinkedList<>();
        }
        queue = new LinkedList<>();
    }

    public void addEdge(int u, int v){
        adj[u].add(v);
    }

    public void bfs(int R){
        queue.add(R);
        visit[R]=true;
        while (!queue.isEmpty()){
            int tmp = queue.poll();
            for(int i : adj[tmp]){
                if(visit[i])continue;
                queue.add(i);
                visit[i]=true;
            }
        }
    }
}