백준 15663 (DFS, 백트래킹, 지역메모리, 함수스코프)

15663번: N과 M (9)

 

과정

• 주어진 숫자를 오름차순으로 정렬 후 (sort)
• 주어진 숫자들 중 M개를 뽑아서 수열을 만든다. (중복X)
• 다만, 이번에는 주어지는 숫자들 중 중복되는 숫자가 있다. : 그래서 같은 수열이 나올 수 있다는 것!
• 그래서 처음에는

• if 문에 number[count] != sortNum[i]를 추가해서
  이미 출력된 이전 수열의 같은 자리 숫자 number[count] vs 현재 집어넣으려는 숫자 sortNum[i]를 비교했다.
• 이 코드의 반례는 다음과 같다.

• 원래라면 1 9 9, 9 1 9, 9 9 1, 9 9 9가 나와야하지만, 9 1 9가 없다.
• 그 이유는 9 1 9가 들어가기 위해  9 1까지 들어가고, 9가 들어가는 상황에서
  이전 수열의 같은 자리 숫자 number[count] vs 현재 집어넣으려는 숫자 sortNum[i]를 비교할 때
  number[2] 는 이전 배열인 1 9 9의 마지막 9가 들어가있기 때문이다.
• 즉, 이전 수열의 숫자가 아닌 수열 전체를 파악하기로 했다.
• 문제가 생겼다.

finalNum을 함수밖에 선언

결과

 

finalNum을 함수 안에 선언

 

결과

• 변수를 DFS()밖에 선언하고 안에서는 0으로 초기화할 때랑 DFS()안에서 초기화할 때랑 답이 다르다..

원인

• 지역 메모리, 전역 메모리, 함수 스코프, 그리고 재귀함수의 정확한 구현 범위의 지식이 부족했다.
• 일단 1번의 경우 전역변수로 선언하고 else문안에서 0으로 넣었다.
  그러면 재귀함수를 돌 때, 1 9 9까지는 잘 들어가겠지만, 내가 생각한 0으로 초기화하는 곳은 애초에 코드가 작동하지 않는다. 왜냐하면 재귀함수 기준 for문안에서만 돌거니까..... 그래서 9가 계속 들어간것.
• 그렇다면 2번은?
  여기서 지역변수 전역변수 스코프 얘기가 나오는데, 일단 지역변수는 스코프 안에서 생성되어 스코프를 나가면 자동으로 소멸된다. (스코프는 { 중괄호} 로 설정한 블록 범위이다.)
  즉, 처음 fianlNum은 0이었다가 1이 넣어져도 DFS로 인해 int fianlNum을 거치게 되면서 같은이름의 fianlNum 지역변수가 0으로 여러개 생기는데 메모리상에서는 이전에 있던 지역변수 위에 위치하게 된다.
  그리고 각각의 finalNum도 9, 9가 들어가겠지.
  근데 count가 다차서 return 되어 반복문이 끝나고, else도 끝나면 지역변수가 생성된 스코프가 끝나고, 해당 변수는 자동으로 소멸한다. 이 과정에서 사라진 변수 밑에 있던 변수가 드러나게 되고, 이게 finalNum 1이 보이게 되는 과정이다.
  밑에 링크를 통해 변수 위에, 밑에 라는 의미를 추가로 학습했다.

구름EDU - 모두를 위한 맞춤형 IT교육

 

코드

#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

    {

        int finalNum = 0;

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

        {

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

            // 이미 출력된 이전 수열의 같은 자리 숫자가

            // cout << "finalNum : " << finalNum <<" count : " << count << " i : " << i << " number[count] : " << number[count] << " sortNum[i] : " << sortNum[i] << "\n";

            if (isVisited[i] == false && sortNum[i] != finalNum)

            {

                isVisited[i] = true;

                number[count] = sortNum[i];

                finalNum = 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);

}