[BOJ] 10451. 순열 사이클(DFS, BFS)

#. Problem

https://www.acmicpc.net/problem/10451

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

생각보다 간단하게 

정점들을 DFS 혹은 BFS로 탐색하면서 

원점으로 돌아오면 사이클이 생성되고,

그 사이클의 개수를 구하는 문제이다.

#. bfs Code

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
 
void solve()
{
    int n, i, a, res = 0;
    scanf("%d", &n);
    vector<vector<int> > g(n + 1);
    vector<int> ck(n + 1);
    queue<int> q;
 
    for (i = 1; i <= n; i++) {
        scanf("%d", &a);
        g[i].push_back(a);
    }
 
    for(i=1;i<=n;i++){
        if (ck[i]) continue;
 
        q.push(i);
        ck[i] = 1;
        
        while (!q.empty()) {
            int now = q.front();
            q.pop();
 
            if (!ck[g[now][0]]) {
                ck[g[now][0]] = 1;
                q.push(g[now][0]);
            }
            else {
                res++;
                break;
            }
        }
    }
 
    printf("%d\n", res);
}
 
int main(void)
{
    int tc;
    freopen("input.txt", "rt", stdin);
    scanf("%d", &tc);
    
    while (tc--) 
        solve();
    
 
    return 0;
}

line 19~38) 각 정점을 탐색

line 20) 이미 방문한 정점이라면 pass

lien 22~23) 방문하지 않은 정점이라면 queue에 넣어주고 check !

line 25~37) queue가 빌 때까지 반복

line 26~27) queue의 가장 앞 원소를 빼낸다.

line 29~31) 현재 정점과 연결된 정점이 방문하지 않은 상태라면

line 30) 방문으로 check 해주고

line 31) 연결된 정점을 queue에 넣어준다

line 33) 현재 정점과 이미 연결된 상태라면 사이클이 생성된 것이므로 cnt 해주고 break;

뭔가 코드가 너무 길어서 최적화를 해보고 싶다...

#. bfs++ Code

#include <cstdio>
#include <string.h>
using namespace std;
 
void solve()
{
    int n, i, j, res = 0;
    int g[1001], ck[1001];
    memset(ck, 0, sizeof(ck));
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++) 
        scanf("%d", g+i);
 
    for (i = 1; i <= n; i++) {
        if (ck[i]) continue;
 
        for (j = i; !ck[j]; j = g[j])
            ck[j] = 1;
 
        res++;
    }
 
    printf("%d\n", res);
}
 
int main(void)
{
    int tc;
    //freopen("input.txt", "rt", stdin);
    scanf("%d", &tc);
 
    while (tc--)
        solve();
 
 
    return 0;
}

line 9) 순열로 주어져서 인접 리스트까지 만들어 줄 필요가 없었다.

line 15~22) 각 정점을 탐색

line 20) 이미 방문한 정점이라면 pass

line 18) 이미 방문한 정점에 도달할 때까지 반복,

line 19) 현재 정점을 방문했다고 check 해주고, 

          반복문은 해당 수열이 저장하고 있는 정점을 가지고 다시 수행

#. dfs Code

#include <cstdio>
#include <string.h>
using namespace std;
 
int g[1001], ck[1001];
 
void dfs(int x)
{
    int i;
    if (ck[x]) return;
 
    ck[x] = 1;
    dfs(g[x]);
}
 
void solve()
{
    int n, i, j, res = 0;
    memset(g, 0, sizeof(ck));
    memset(ck, 0, sizeof(ck));
    scanf("%d", &n);
 
    for (i = 1; i <= n; i++)
        scanf("%d", g + i);
 
    for (i = 1; i <= n; i++) {
        if (ck[i]) continue;
 
        dfs(i);
        res++;
    }
 
    printf("%d\n", res);
}
 
int main(void)
{
    int tc;
    // freopen("input.txt", "rt", stdin);
    scanf("%d", &tc);
 
    while (tc--)
        solve();
 
    return 0;
}

line 26~31) 각 정점을 탐색

line 27) 이미 방문한 정점이라면 pass

line 29) dfs 호출

line 7~14) dfs

line 10) 사이클이 완성되면 return

line 12~13) 현재 정점을 방문했다고 check해주고 해당 수열이 저장하고 있는 정점과 함께 dfs 호출

line 30) cnt