백준 15650 N과M (2) C++ 풀이 (무조건 이해시켜드림)

안녕하세요~ 프루니입니다~

오늘 풀어볼 문제는 백준 15650 N과M(2) 입니다!!

N과M 시리즈를 주르륵 올릴 예정인데 N과M(1) 부터 보고 오신다면 더 빠르게 이해가 되실 것 같아요!!

 

자!! 그럼 문제 뿌시러 가주아!!!!!!!!!!!!!!!!!!!!!

---

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

---

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

---

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

---

프루니의 풀이

사용 언어 : C++

사용 알고리즘 : 브루트포스

 

문제 해석

1~N까지의 숫자 중에 M개를 뽑아 오름차순으로 나열하는 순열 문제입니다. 중복은 허용하지 않습니다.

이 문제는 모든 경우를 모두 출력해야하기 때문에 브루트포스를 사용해야 합니다.

!여기서 잠깐! 호옥시 브루트포스에 대해 모르시는 분들이 있다면 보세용! (사실 제가 몰랐어용 히히)

 

브루트포스가 뭐죵?

브루트포스는 모든 경우를 하나도 빠짐없이 직접 다 실행하는 것이랍니다!

 

나무위키에 따르면

"브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다." 라고 합니다!

 

모든 경우를 다 돌아봐야 하는 문제라면 브루트포스 알고리즘을 쓰면 되겠어용!

 

문제 풀이

자 해당 문제를 브루트포스를 사용하여 코드로 구현하는 방식은 두가지 입니다.

첫번째는 재귀, 두번째는 반복문이에요~

프루니는 재귀를 선호하여 재귀함수로 구현했어요!

하지만 반복문을 원하시는 분들이 계시다면 반복문으로도 구현하여 올릴게요!! 댓글로 요청주세요~ 바아로 갑니다!

 

일단 재귀든 반복문이든 문제를 해결하기 위해 진행되는 흐름은 같아요!

M개의 숫자를 뽑을 때마다 출력하는 동작을 경우의 수가 끝날때까지 반복하면 된답니다!

아래 그림은 M개의 숫자를 뽑는 루틴을 표현한 그림이에요~

M개의 숫자를 뽑을 때마다 2가지 조건을 체크하면 되는데,

첫번째로 이미 뽑았던 숫자인지이고 두번째로 직전에 뽑은 숫자보다 큰숫자인지 검사하면 된답니다!

 

위 패턴을 코드로 구현하기 위해 먼저 배열 2개가 필요해요!

첫번째 배열은 어떤 숫자가 이미 뽑았던 숫자인지 아닌지를 저장하고 있는 bool형 배열이고

두번째 배열은 지금까지 뽑은 숫자를 저장하고 있는 int형 배열이에요~

 

프루니는 첫번째 배열 이름을 visited, 두번째 배열이름을 sequence라고 설정했어요~

 

visited는 처음에 모든 요소가 false로 초기화 되어있고 뽑힌 숫자에 해당하는 요소는 true로 설정해준답니다!

sequence에는 현재 뽑은 숫자를 추가해주면 되어요~

 

자 이제 코드를 볼게요~ 

 

재귀로 구현한 코드!

주석으로 설명할게요~

 

#include <iostream>
#include <vector>

using namespace std;
#define MAX 9

bool visited[MAX];
int sequence[MAX];
int N, M;

//재귀함수
//매개변수 cnt는 현재 뽑아야하는 숫자의 순번이에요! 
//이미 2개를 뽑았고 3번째 숫자를 뽑을 차례라면 cnt에 3을 넣어 함수를 호출하면 됩니다!
void DFS(int cnt)
{
    //재귀함수 탈출조건 : m개 다 뽑을 때 출력 후 return
    if (cnt == M)
    {
        for (int i = 0; i < M; ++i)
        {
            cout << sequence[i] << ' ';
        }
        cout << '\n';
        return;
    }

    //1~N까지의 숫자를 모두 돌며 각 숫자가 이미 뽑힌 숫자인지 검사하고 뽑힌적없는 숫자이면 뽑는 반복문입니다~
    for (int i = 1; i <= N; ++i)
    {
        if (!visited[i]) // i가 이미 뽑힌 숫자인지 검사합니다. visited의 i번째 요소가 false라면 뽑을 수 있어요!
        {
            if (cnt == 0 || sequence[cnt - 1] < i) // 오름차순이기때문에 직전에 뽑은 숫자보다 현재 숫자 i가 클때만 추가해요!
            {
                sequence[cnt] = i; // 현재 뽑고있는 순서의 숫자로 i를 추가해요!
                visited[i] = true; // 이제 i는 뽑힌 숫자가 되기때문에 뽑힌 숫자라고 표시하기 위해 visited의 i번째 요소를 true로 설정해요!
                DFS(cnt + 1); // M개의 숫자 중에서 cnt번째 숫자까지 뽑았으니까 그다음 숫자인 cnt+1번째 숫자를 뽑기위해 cnt+1을 매개변수로 DFS함수를 호출해요~
                visited[i] = false; //M개의 숫자를 다 뽑고 이제 또 처음부터 M개의 숫자를 뽑기 시작해야하므로 뽑힌 숫자 기록을 지워줍니다!
            }
        }
    }
}

int main()
{
    cin >> N >> M; // N, M을 입력받아요~

    DFS(0); // 재귀함수 시작!
    return 0;
}

 

자! 아까 브루트포스로 푼다면서 갑짜기!!!!! DFS라는 단어가 등장해서 어이가 없는 분들을 위해 설명을 드리자면!!! 

 

DFS는 한번 방문했던(뽑았던) 숫자에는 다시는 방문하지 않기 때문에 visited배열의 요소가 true로 설정되는 순간 다시 false로 변경되는 경우가 없이 그것으로 끝이랍니다!

하지만 이 코드에서는 DFS처럼 visited배열의 요소를 true로 설정한 후, DFS에서 탈출 조건을 만족하여 return되고 다시 DFS함수가 호출되기전에!! visited배열의 요소를 false로 되돌려주는 코드가 있어요!!!!!!!!!!!

 visited[i] = false;

바로 이것!!

 

따라서 M개의 숫자를 모두 뽑은 후 출력하고, 또다른 경우의 M개의 숫자를 뽑을때 visited 배열의 요소가 모두 false가 되어 또 뽑힐 수 있답니다! 그래서 모든 경우의 수를 모두 도는 브루트포스가 되는 것이에요!!!

 

끗!

---

 

여러분 고생많으셨어요~

이해가 되셨다면 공감버튼 한번씩 눌러주세요(꾸벅)

이해가 안되셨다면 댓글로 질문해주세요!!! 바아로 갑니다.

 

될때까지 하면 됩니다.

반드시 뿌십시다!!

 

자 그럼 저는 또 다음 문제를 가지고 올게요~ 

안녕~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~