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

🔺 문제

10451번: 순열 사이클

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int T, N, cnt;
    static int[] A; // 점 저장 배열
    static boolean[] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        T = Integer.parseInt(br.readLine());
        while(T --> 0) {
            N = Integer.parseInt(br.readLine());
            
            // 변수들 초기화
            A = new int[N + 1];
            visited = new boolean[N + 1];
            cnt = 0;
            
            // 입력받기
            st = new StringTokenizer(br.readLine(), " ");
            for(int i = 1 ; i <= N ; i++) {
                A[i] = Integer.parseInt(st.nextToken());
            }
            
            for(int i = 1 ; i <= N ; i++) {
                if(!visited[i]) {
                    dfs(i);
                    cnt++;    // 🔔 사이클 개수 = 정점들의 집합 개수 🔔
                }
            }
            sb.append(cnt).append("\n");
        }
        
        System.out.println(sb);
    }
    
    private static void dfs(int num) {
        if(visited[num])    return;
        
        visited[num] = true;
        
        if(!visited[A[num]]) {
            dfs(A[num]);
        }
    }
}
 

✅ 해결 아이디어
✔ DFS
- 사이클 개수 = 정점들의 집합 개수 =  DFS 함수 호출 횟수

 

 

 

---

🔺 다른 풀이들

- dfs를 int형으로 받아서 1이나 0 리턴하게... 그리고 그 횟수를  cnt에 더함

로그인

---

💬 느낀 점

리스트로 받으려고 했는데

생각해보니까 순열이 N개로 이뤄져있으니까 수끼리 겹칠 일이 없으니까

배열로 해도 되는 것이었당.....

 

DFS 오랜만에 쓰면 또 까먹는....ㅠ

 

DFS나 BFS는 문제들 나오는 유형은 크게 다르지 않은 것 같은데

말을 어떻게 하느냐에 따라.. 괜히 헤매게 되는 거 같다.😭

 

 + 이번 삼성DX 하계 알고리즘 특강 1번 문제도 사이클 여부 판단하는 거 써야했던 거 같은디...

1회독	2회독	3회독	4회독	5회독
V	8.4

 

(+8.4 2회독)

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int T, N, cnt;
    static int[] A;
    static boolean[] visited;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        
        T = Integer.parseInt(br.readLine());
        while(T --> 0) {
            N = Integer.parseInt(br.readLine());
            
            A = new int[N + 1];
            visited = new boolean[N + 1];
            cnt = 0;
            
            st = new StringTokenizer(br.readLine(), " ");
            for(int i = 1 ; i <= N ; i++) {
                A[i] = Integer.parseInt(st.nextToken());
            }
 
            for(int i = 1 ; i <= N ; i++) {
                if(!visited[i]) {
                    dfs(i);
                    cnt++;
                }
            }
            sb.append(cnt).append("\n");
        }
        
        System.out.println(sb);
    }
    
    private static void dfs(int num) {
        if(visited[num]) return;
        
        visited[num] = true;
        if(!visited[A[num]]) {
            dfs(A[num]);
        }
    }
}

 

---

(참고)

✔ 풀이 참고

[백준] 10451 - 순열 싸이클 (JAVA)

 

 

✔ 그래프에서 사이클 찾기

[알고리즘] 그래프(Graph)에서 사이클(Cycle) 찾기