[백준(BOJ)] 10451번: 순열 사이클 (DFS/BFS, C++)

📝 문제풀이 과정

---

순열 사이클은 시작 후 자기 자신으로 다시 돌아온다.

1	2	3	4	5	6	7	8
3	2	7	8	1	4	5	6

주어진 예시를 보면, index마다 값이 주어지는데, 각 인덱스에서 값의 방향으로 간선이 존재한다.

이것으로 그래프의 연결성을 나타낼 수 있고, 1 -> 3, 3 -> 7, 7 -> 5, 5 -> 1로 1로 시작해서 1로 다시 돌아오므로 순열 사이클에 해당한다.

2의 경우에도 2에서 시작해서 2로 끝나므로 하나의 순열 사이클이다.

4 -> 8 -> 6 -> 4이므로 이 경우에도 하나의 순열 사이클로, 이 테스트케이스에는 총 3개의 순열 사이클이 존재한다.

방향 그래프이고, 모든 정점이 연결되어 있진 않으므로 모든 인덱스에 대해 방문하지 않았으면 BFS로 방문해서 탐색하도록 한다.

이미 방문 했고, current와 인접한 next 정점이 초기 정점 (start)와 동일하다면 순열 사이클에 해당하므로 count를 증가하고 리턴한다.

#include <stdio.h>
#include <deque>
#include <queue>
using namespace std;

void BFS(int start, deque<int> *graph, int *visited, int *count){
    queue<int> q;
    visited[start] = true;
    q.push(start);
    printf("[+] %d visited\n", start);

    while(!q.empty()){
        int current = q.front();
        q.pop();
        for(int next: graph[current]){
            if(visited[next] == false){
                visited[next] = true;
                q.push(next);
                printf("[+] %d visited\n", next);
            }
            else if(visited[next] == true && next == start){
                (*count)++; // 이미 방문했고, 인접한 정점이 처음 방문한 정점이면 사이클이므로 카운팅
                printf("[+] %d visited count: %d\n", next, *count);
                return;
            }
        }
    }
    

}

int main(){
    int T;
    scanf("%d", &T);

    for(int i=0; i<T; i++){
        int N, count=0;
        scanf("%d", &N);
        deque<int> graph[N+1];
        int visited[N+1];
        fill(visited, visited+N+1, false);

        for(int j=1; j<=N; j++){
            int num; scanf("%d", &num);
            graph[j].push_back(num);
        }
        for(int j=1; j<=N; j++){
            printf("graph[%d]: ", j);
            for(int n: graph[j]) printf("%d ", n);
            printf("\n");
        }
        for(int j=1; j<=N; j++){
            if(visited[j] == false) BFS(j, graph, visited, &count);
        }
        printf("%d\n", count);
    }
}

 

 

💻 C++ 제출코드

---

#include <bits/stdc++.h>
using namespace std;

void BFS(int start, deque<int> *graph, int *visited, int *count){
    queue<int> q;
    visited[start] = true;
    q.push(start);

    while(!q.empty()){
        int current = q.front();
        q.pop();
        for(int next: graph[current]){
            if(visited[next] == false){
                visited[next] = true;
                q.push(next);
            }
            else if(visited[next] == true && next == start){
                (*count)++; // 이미 방문했고, 인접한 정점이 처음 방문한 정점이면 사이클이므로 카운팅
                return;
            }
        }
    }
    

}

int main(){
    int T;
    scanf("%d", &T);

    for(int i=0; i<T; i++){
        int N, count=0;
        scanf("%d", &N);
        deque<int> graph[N+1];
        int visited[N+1];
        fill(visited, visited+N+1, false);

        for(int j=1; j<=N; j++){
            int num; scanf("%d", &num);
            graph[j].push_back(num);
        }

        for(int j=1; j<=N; j++){
            if(visited[j] == false) BFS(j, graph, visited, &count);
        }
        printf("%d\n", count);
    }
}

 

 

👏 결과

---