백준 10451 번 - 순열 사이클 (C++/BFS/DFS/그래프)

 

문제

접근법

문제만 이해하면 접근법은 쉽다.

처음에 3,2,7,8,1,4,5,6 만 입력을 받고 그래프로 어떻게 표현하지를 생각하는데 시간이 오래걸렸다.

예시를 잘 보면



위쪽은 배열의 Index, 아래쪽은 입력한 수 이므로,

adjacants[from][to] 라고 가정했을때 (adjacants는 그래프간의 연결을 나타냄),

from = 배열의 Index

to = 입력받은 수

를 넣어주면 된다

 

그 이후는 BFS코드를 그대로 사용한다. 

visited를 만들어서 q에 시작위치 하나를 먼저 저장한후, 

q.front(),q.push()를 반복하며 순회해준다.

 

사이클 수는 간단하다. 밑에서 BFS를 호출할때 for문에 넣어줘서 if(visited[i]==false) 일 때 순회하는데 

만약 visited[1]이 false라면 이는 0번 노드와 연결되어 있지 않아서 BFS내부에서 체크를 해주지 않은 것이다.

즉 if(visited[i]==false) 이 조건을 만족할 때마다 cnt를 ++ 해주면 된다.

 

밑에는 BFS,DFS 버전 각각 적어둔 코드이다.

코드

BFS ver.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void BFS(vector<vector<int>>& adjacants, vector<bool>& visited, int here)
{
    queue<int> q;
    q.push(here);
    visited[here] = true;
    while (!q.empty())
    {
        int there = q.front(); q.pop();
        visited[there] = true;
        for (int adj : adjacants[there])
        {
            if(visited[adj] == false)
                q.push(adj);
        }

    }
}

int main()
{
    int N;
    vector<int> ansList;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int M;
        int numCycle = 0;
        cin >> M;
        vector<vector<int>> adjacants(M);
        for (int j = 0; j < M; j++)
        {
            int num;
            cin >> num;
            adjacants[j].push_back(num - 1);
        }
        vector<bool> visited(M, false);
        for (int j = 0; j < M; j++)
        {
            if (visited[j] == false)
            {
                numCycle++;
                BFS(adjacants, visited, j);
            }
        }
        ansList.push_back(numCycle);
    }
    for (int i = 0; i < ansList.size(); i++)
    {
        cout << ansList[i] << "\n";
    }
}

 

DFS ver.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void DFS(vector<vector<int>>& adjacants, vector<bool>& visited, int here)
{
    visited[here] = true;
    for (int i = 0; i < adjacants[here].size(); i++) {
       int there =  adjacants[here][i];
       if (visited[there] == false)
       {
           DFS(adjacants, visited, there);
       }
    }
}

int main()
{
    int N;
    vector<int> ansList;
    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int M;
        int numCycle = 0;
        cin >> M;
        vector<vector<int>> adjacants(M);
        for (int j = 0; j < M; j++)
        {
            int num;
            cin >> num;
            adjacants[j].push_back(num - 1);
        }
        vector<bool> visited(M, false);
        for (int j = 0; j < M; j++)
        {
            if (visited[j] == false)
            {
                numCycle++;
                DFS(adjacants, visited, j);
            }
        }
        ansList.push_back(numCycle);
    }
    for (int i = 0; i < ansList.size(); i++)
    {
        cout << ansList[i] << "\n";
    }
}

위가 DFS, 아래가 BFS 으로 제출한것이다.

DFS가 미세하게 빠르게 나왔다.