10451번

10451번 - 순열 사이클

1년 전에 이 문제를 풀었는데 그 때 그 코드를 보니 무슨 생각없이 푼 것 같은데 맞았다... 그때는 그냥 무작정 풀었던 것 같다..

문제 풀때

-> DFS, BFS 안에 있는 for문 안에서 처음에 if (next != start) 이 부분을 빼먹어서 노드 한개가 혼자 순환하는 것을 캐치해내지 못했었다.

    디버깅을 통해서 발견했다. 이런 예외적인 부분을 꼼꼼히 생각해서 푸는 연습. 완벽하게 풀기.

-> 혹시 dfs 돌렸지만 순환함수를 발견하지 못할 수도 있기 때문에 cnt의 값을 나중에 확인하고 증가시켜 주었다.

-> 모든 노드에 대해서 BFS , DFS 를 실행시켰다. 연결 요소가 존재하기 때문에.

-> BFS, DFS 를 돌릴 때 세가지 CASE

    1. 다음 노드가 한번도 탐색 안한 노드일 경우 - 탐색

    2. 다음 노드가 탐색 했는데 나랑 같은 사이클 cnt 인 경우 - 순환

    3. 다음 노드가 지금 노드일때 - 순환

< BFS 정답 코드 >

#include<iostream>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;
 
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int N;
        int cnt = 0;
        bool isRotate;
        vector<int> v[1001];
        int check[1001];
 
        cin >> N;
 
        for (int i = 1; i <= N; i++)
        {
            v[i].clear();
        }
        memset(check, 0, sizeof(check));
 
 
        for (int i = 1; i <= N; i++)
        {
            int a;
            cin >> a;
            v[i].push_back(a);
        }
 
        for (int i = 1; i <= N; i++)
        {
            isRotate = false;
            if (check[i] == 0 && !isRotate)
            {
                queue<int> q;
                q.push(i);
                check[i] = cnt + 1;
 
                while (!q.empty() && !isRotate)
                {
                    int now = q.front();
                    q.pop();
 
                    for (int i = 0; i < v[now].size(); i++)
                    {
                        int next = v[now][i];
 
                        if (now == next)
                        {
                            isRotate = true;
                            break;
                        }
                        else
                        {
                            if (check[next] == 0)
                            {
                                q.push(next);
                                check[next] = check[now];
                            }
                            else if(check[next]!=0 && check[next]==check[now])
                            {
                                isRotate = true;
                                break;
                            }
                        }
                    }
                }
            }
 
            if (isRotate)
            {
                cnt += 1;
            }
        }
 
        cout << cnt << endl;
    }
    return 0;
}

< DFS 정답 코드 >

#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
bool isRotate;
vector<int> v[1001];
int check[1001];
void dfs(int start)
{
    if (!isRotate)
    {
        for (int i = 0; i < v[start].size(); i++)
        {
            int next = v[start][i];
 
            if (next != start)
            {
                if (check[next] == 0)
                {
                    check[next] = check[start];
                    dfs(next);
                }
                else if (check[next] != 0 && check[next] == check[start])
                {
                    isRotate = true;
                    break;
                }
            }
            else
            {
                isRotate = true;
                break;
            }
        }
    }
 
    return;
}
int main()
{
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        int N;
        int cnt = 0;
        cin >> N;
        for (int i = 1; i <= N; i++)
        {
            v[i].clear();
        }
        memset(check, 0, sizeof(check));
 
        for (int i = 1; i <= N; i++)
        {
            int a;
            cin >> a;
            v[i].push_back(a);
        }
 
        for (int i = 1; i <= N; i++)
        {
            isRotate = false;
            if (check[i] == 0 && !isRotate)
            {
                check[i] = cnt + 1;
                dfs(i);
                if (isRotate)
                {
                    cnt += 1;
                }
            }
        }
 
 
        cout << cnt << endl;
    }
 
    return 0;
}