[백준/BOJ] - 10451번 순열 사이클 (C++/DFS)

 

 

01. 문제

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

---

 

 

 

 

 

 

 

문제설명

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3& 2&7&8&1&4&5&6 \end{pmatrix}\) 와 같다. 또는, Figure 1과 같이 방향 그래프로 나타낼 수도 있다. 순열을 배열을 이용해 \(\begin{pmatrix} 1 & \dots & i & \dots &n \\ \pi_1& \dots& \pi_i & \dots & \pi_n \end{pmatrix}\) 로 나타냈다면, i에서 πi로 간선을 이어 그래프로 만들 수 있다. Figure 1에 나와있는 것 처럼, 순열 그래프 (3, 2, 7, 8, 1, 4, 5, 6) 에는 총 3개의 사이클이 있다. 이러한 사이클을 "순열 사이클" 이라고 한다. N개의 정수로 이루어진 순열이 주어졌을 때, 순열 사이클의 개수를 구하는 프로그램을 작성하시오.

 

 

---

 

 

02. 문제 접근 과정 📖

김동빈 저자의 이것이 코딩테스트다 책 의 나오는 149페이지의 나오는 얼음틀? 문제랑 똑같이 풀면 될 것 같다.


테스트 케이스로 1000으로 별로 안크고 순열이므로 DFS.... 로 풀면 될 것 같

 

 

테스트 케이트 예제 입력 1 번으로 사이클을 구상해 보면 이렇게 나

 

가 아니라 노드를 1부터 계산하면 문제 설명과 똑같이 나온다.

 

 

 

bool dfs(int _startX = 1)
{
    visitFlag[_startX] = true;

    for(const auto x : graph[_startX])
    {
	    if(!visitFlag[x])
	    {
            dfs(x);
            return true;
	    }
        return false;
    }
    return false;
}

기존 코드로 하니까 자기 자신의 사이클을 판단할 수 없다 

 

 

 

그러므로 자기 자신의 사이클도 판단할 수 있게 만들어 주자.

 

 

bool dfs(int _startX)
{
    visitFlag[_startX] = true;

    for (const auto x : graph[_startX])
    {

        if (_startX == x)
        {
            return true;
        }


        if (!visitFlag[x])
        {

            dfs(x);
            return true;
        }
        return false;
    }
    return false;
}

 

 

 

---

 

03. 문제 풀이 ✏️

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

using namespace std;

int testCases, numNodes;
int currentNode, targetNode;

vector<vector<int>> adjacencyList;   //입력
vector<bool> visited;                //방문 확인 

vector<int> result;

bool dfs(int startNode) 
{
    visited[startNode] = true;

    for (const auto neighbor : adjacencyList[startNode])
    {
        if (startNode == neighbor)
        {
            return true;
        }

        if (!visited[neighbor])
        {
            dfs(neighbor);
            return true;
        }
        return false;
    }
    return false;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int cycleCount;             //사이클 카운트

    cin >> testCases;

    for (int i = 0; i < testCases; ++i)
    {
        cycleCount = 0;

        cin >> numNodes;


        //초기화
        adjacencyList.clear();
        fill(visited.begin(), visited.end(), false);

        adjacencyList.resize(numNodes + 1);
        visited.resize(numNodes + 1, false);
        //

        //입력
        for (int j = 1; j <= numNodes; ++j) {
            cin >> currentNode;
            adjacencyList[j].push_back(currentNode);
        }


        //사이클 탐색
        for (int j = 1; j <= numNodes; ++j)         
        {
            if (dfs(j))
            {
                ++cycleCount;
            }
        }


        //정답 push
        result.push_back(cycleCount);
    }


    //정답 출력
    for (auto count : result)
    {
        cout << count << '\n';
    }

    return 0;
}

 

 

단순하게 DFS 구현하고 자기 자신 부분만 추가하면 된다~

---

04. 결론

맨 처음에 <=을 <로 써서 3시간 동안 찾고 있었다...

디버깅 할때 끝까지 안하고 중간만 판단해서 끝 부분이 안들어갈줄은 몰랐다...

앞으로 디버깅을 끝까지 하자..