[Baekjoon] 순열 사이클(BOJ 10451)

👀 문제 설명

문제

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면

와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다.

순열을 배열을 이용해

로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다.

Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다.

N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

 

출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

 

예제 입력 1

2

8

3 2 7 8 1 4 5 6

10

2 1 3 4 5 6 7 9 10 8

 

예제 출력 1

3

7

 

✍🏻풀이

BFS 혹은 DFS로 푸는 문제라고 생각했다.

BarkingDog 은 큐를 사용해 BFS를 구현하기 때문에 나도 큐를 사용했다.

그런데 문제가 내가 꼬아서 푼 것 같기도 하고 아무튼 재귀 사용하는게 훨씬 코드가 깔끔하다!

 

코드

Queue 사용, 재귀 X

//
//  BOJ_10451.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/10/22.
//  Copyright © 2020 조수민. All rights reserved.
//
//  순열 사이클(https://www.acmicpc.net/problem/10451)

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

/**
 [예제 입력 1]
 2
 8
 3 2 7 8 1 4 5 6
 10
 2 1 3 4 5 6 7 9 10 8
 */
int T;
vector<int> N; // N에는 {8, 10}
vector<vector<int>> numbers; // numbers에는 { { 3, 2, 7, 8, 1, 4, 5, 6 }, { 2, 1, 3, 4, 5, 6, 7, 9, 10, 8 } };


void input() {
    cin >> T;
    N.resize(T);
    numbers.resize(T);
    
    for (int i = 0; i < T; i++) {
        cin >> N.at(i);
        
        numbers.at(i).resize(N.at(i));
        for (int j = 0; j < numbers.at(i).size(); j++) {
            int number;
            cin >> number;
            numbers.at(i).at(j) = number - 1;
        }
    }
}

/**
 size = 8이 들어오고, nums = { 2, 1, 6, 7, 0, 3, 4, 5 } 일 경우
 */
int getCycleNum(int size, vector<int> nums) {
    int answer = 0;
    
    vector<bool> check;
    check.resize(size);
    check.assign(check.size(), false); // check 벡터를 모두 false로 초기화한다.
    
    queue<int> Q;
    check.at(0) = true; // index 0은 방문 (1)
    Q.push(0);
    
    /**
     check 벡터의 모든 값이 true라면 다 확인한 것이다.
     -> while문에서 빠져나와야 함
     */
    bool isTrue = true; // check벡터의 모든 값이 true인지 확인하는 flag
    int noneIndex = -1;
    bool turnEnd = false;
    
    while (true) {
//        for (int i = 0; i < check.size(); i++) {
//            cout << i << " : " << (check.at(i) ? "true" : "false") << " ";
//        }
        
        for (int i = 0; i < check.size(); i++) {
            
            
            if (check.at(i) == false) { // 하나라도 체크하지 않았으면
                noneIndex = i;
                isTrue = false; // isTrue를 false로 바꾼다. (true일 때 while문이 끝남)
                
//                cout << i << " : false" << " ";
                break;
            }
            else {
                isTrue = true;
//                cout << i << " : true" << " ";
            }
        }
        cout << endl;
        
        if (isTrue == true) {
            break;
        }
//        cout << "noneINdex : " << noneIndex << endl;
        
        /**
         isTrue가 false라는 뜻 (다 돌지 않았다)
         */
        if (Q.empty() && noneIndex != -1) { // 큐가 비어있을 때 (하나으 ㅣ사이클이 끝)
            check.at(noneIndex) = true;
            Q.push(noneIndex);
            continue;
        }
        else { // 큐에 무언가가 있을 때
            int curFrom = Q.front(); Q.pop(); // 0 이라면
            int curTo = nums.at(curFrom); // 2
            
            // 이미 방문했다
            if (check.at(curTo) == true) {
                turnEnd = true;
                answer++;
                continue;
            }
            // 방문을 안했으면
            else {
                check.at(curTo) = true; // 방문을 했다고 바꿔주고
                Q.push(curTo);
            }
            
        }
        
        cout << "answer : " << answer << endl;
    }
    answer++; // 왜인지 마지막 턴은 +1을 안한다,,
    
    return answer;
}

int main() {
    input();

    for (int i = 0; i < N.size(); i++) {
        cout << getCycleNum(N.at(i), numbers.at(i)) << endl;
//        cout << N.at(i) << endl;
//
//        for (int j = 0; j < numbers.at(i).size(); j++) {
//            cout << numbers.at(i).at(j) << " ";
//        }
//        cout << endl;
    }
    
//    cout << getCycleNum(10, { 1, 0, 2, 3, 4, 5, 6, 8, 9, 7 });
    
    return 0;
}

DFS(재귀 사용)

//
//  BOJ_10451_using_recurrence.cpp
//  Algorithm
//
//  Created by 조수민 on 2020/10/23.
//  Copyright © 2020 조수민. All rights reserved.
//
//  순열 사이클(https://www.acmicpc.net/problem/10451)
//  재귀 사용 [참고] https://kyunstudio.tistory.com/125

#include <stdio.h>
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

/**
 나는 vector를 사용했는데 이 답은 배열을 사용했다.
 */
int arr[1001];
bool visited[1001];

// DFS 구현
void DFS(int i) {
    if (visited[i]) // 방문했으면
        return; // 끝
    
    // 방문하지 않았으면
    visited[i] = true;
    DFS(arr[i]); // 재귀
}

int findCycles(int N) {
    // 초기화
    memset(visited, false, sizeof(visited)); // 배열의 모든 값을 false로 초기화한다. (memset 함수 사용!!)
    
    int count = 0;
    /**
     내가 푼 풀이는 입력받은 값을 넣을 때 -1 했는데
     그럴 필요 없이 index를 1부터 시작하면 되는 거였다,,!
     */
    for (int i = 1; i <= N; i++) {
        // 배열 중에 아직 선택이 안된 것이 있다면
        if (!visited[i]) {
            // DFS를 해서 사이클 고리를 찾아낸다.
            DFS(i);
            // 그리고 사이클 1개 추가
            count++;
        }
    }
    
    return count; // 사이클 개수 반환
}

int main() {
    int T, N;
    cin >> T;
    
    while (T--) {
        cin >> N;
        
        for (int i = 1; i <= N; i++) {
            cin >> arr[i];
        }
        
        cout << findCycles(N) << endl; // 사이클 개수 찾기
    }
    
    return 0;
}