백준 15654 (DFS, 백트래킹, 정렬)

15654번: N과 M (5)

과정

[C++/백준문제] - 백준 15650, 15652 (DFS)

백준 15650, 15652 (DFS)

이거랑 비슷한 문제인데

• 1부터 시작이 아니다. : 때문에 오름차순으로 정렬을 해줘야한다.
• 본인은 포함하지 않은 채 수열 자체가 오름차순일 필요가 없다. : 하나의 수열에 중복되는 수가 없기만 하면 된다.

이 두가지가 달랐다.

 

정렬의 경우 sort를 이용했고, 중복되는 수를 빼기 위해 isVisited로 방문 여부를 파악했다.

 

삽질한 부분은 백트래킹을 고려하지 않아서 DFS 함수 뒤에  isVisited를 false로 다시 풀어주지 않았다는 것이다..

 

그래서 처음에는 "아 이거 말고 number벡터 자체에서 해당 숫자가 있는지 파악해야겠다" 라고 생각했다.

그래서 find를 이용해서 number내에 sortNum이 있는지 파악했는데, number을 출력해보니 초기화를 따로 해주지 않아서 number에는 이전 값들이 들어있었다. 

 

특히, 오름차순으로 정렬했기 때문에 마지막 숫자의 경우 무조건 number에 있어서 마지막 숫자의 DFS가 작동하지 않았다.

코드

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int N = 0;  // 1~N

int M = 0;  // 1줄당 M개의 숫자를 가진 수열

vector<int> sortNum;    // 받은 숫자를 정렬

// number[i] = j : number자체가 하나의 수열이 된다.(재활용할거임)

// 하나의 수열에서 i번째 숫자가 j가 된다.

vector<int> number; // 숫자를 넣어둘 벡터

vector<bool> isVisited;

void DFS(int start, int count)

{

    // 원하는 숫자만큼 수열을 채웠으면 출력

    if(count == M)

    {

        for (int i = 0; i < M; i++)

            cout << number[i] << " ";

        cout << "\n";

    }

    // 원하는 숫자만큼 수열을 채울때까지 수열 채우기

    else

    {

        for (int i = 1; i < N+1; i++)

        {

            // 해당 수열에 숫자를 포함하지 않았으면,

            if (isVisited[i] == false)

            {

                isVisited[i] = true;

                number[count] = sortNum[i];

                DFS(i+1, count+1);

                // DFS가 한번 끝나고 다시 돌아올 때(백트래킹)

                // isVisited를 false로 만들어줘서 number에는 숫자가 있더라도 없는 것처럼 구현

                // 초기화!! 딱 초기화 같은 느낌

                isVisited[i] = false;

            }

        }

    }

}

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(nullptr); cout.tie(nullptr);

    cin >> N >> M;

    number.resize(N+1, 0);

    sortNum.resize(N+1, 0);

    isVisited.resize(N+1, false);

    for (int i = 0; i < N; i++)

    {

        cin >> sortNum[i];

    }

    sort(sortNum.begin(), sortNum.end());

    DFS(1,0);

}