[10451] 순열 사이클(C++)

문제

10451번: 순열 사이클

 

 

해결 방법

계속 런타임 에러가 떠서 for문이 너무 많은건가.... 변수형을 잘못 선언했나..... 한참을 찾아보고 질문도 올려보고 검색도 해봤는데

그냥 배열의 크기를 잘못 설정해서 그런거였다ㅋㅋ

문제에서 순열의 크기는 최소 2, 최대 1000 이라고 했는데

이걸 착각하고 배열의 크기는 1000-2+1해서 999면 충분하다고 생각했다. 왜 그랬지?

아무튼 그래프 정점의 시작 노드는 1번으로 설정했기 때문에 순열의 크기가 1000이라면

최소 1001 크기의 배열이 필요한 것이다.

그리고 가장 중요한 초기화!!

testcase를 돌 때마다 벡터 a배열, check 배열, cnt를 모두 초기화 해줘야 한다.

또한, queue q 를 bfs 함수의 첫 줄에서 선언해도 되지만,

bfs가 선언될 때마다 q를 매번 생성해줘야 하므로 아예 전역으로 선언해놓고 main에서 초기화 해주는 것이 낫다.

이때 while(!q.empty()) q.pop(); 을 사용해서 q의 모든 원소를 제거해주면 된다.

 

 

내 코드(C++)

// [10451] 순열 사이클
// https://www.acmicpc.net/problem/10451
// dfs, bfs
/* ***순열의 크기는 최대 1000이고 그래프의 index는 1부터 시작하기 때문에 
   배열의 크기는 최소 1001로 잡아야 함*** */

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

void bfs(int s);
bool check[1001];
vector<int> a[1001];
int n, cnt;
queue<int> q;

int main(void)
{
    int t, v;
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> n;

        // initialization
        memset(check, false, sizeof(check));

        while (!q.empty())
            q.pop();

        for (int j = 1; j <= n; j++) {
            a[j].clear(); // initialization
            cin >> v;
            a[j].push_back(v);
        }

        for (int i = 1; i <= n; i++) {
            if (check[i] == false) {
                bfs(i);
            }
        }

        cout << cnt << endl;
        cnt = 0;
    }
    return 0;
}

void bfs(int s)
{
    check[s] = true; q.push(s);

    while (!q.empty()) {
        int x = q.front(); q.pop();

        for (int i = 0; i < a[x].size(); i++) {
            int next = a[x][i];
            if (check[next] == false) {
                check[next] = true; q.push(next);
            }
        }
    }

    cnt++;
}