[BOJ/백준] 15663 N과 M (9)

● [문제번호 15663] N과 M (9)

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

15663번: N과 M (9)

 

● 알아야 할 것

: DFS (깊이 우선 탐색)

: 재귀

 

● 풀이 과정

: N과 M (5) 에서 input 배열에 입력되는 숫자가 중복된다는 점을 고려해야한다.

그 외는 동일한 로직이다.

 

: 각 재귀의 반복문에서 방금 추가한 값을 기억해서 연속된 중복값이 나오지 않게 만든다.

(사진은 해당 문제의 '예시 입력2' 이다)

4 2

9 7 9 1

빨간 상자의 값을 before가 기억해서 파랑상자는 출력하지 않게 만든다

 

● 주의 할 것

: NULL

 

● 참고 할 것

: 풀이과정 참고

https://myunji.tistory.com/309

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// input : 입력된 숫자들
// num : 출력할 숫자 저장
// visited : num 배열에 존재하는 지 확인 (true : 있음 / false : 없음)
int input[9] = {0, };
int num[9] = {0, };
bool visited[9] = {false, };
int N, M;

// 재귀를 이용한 DFS
void NM(int cnt)
{
    // M개 숫자를 저장한 경우
    if(cnt == M)
    {
        // num 배열의 숫자를 순서대로 출력
        for(int i = 1; i <= M; i++)
            cout << num[i] << " ";
        cout << "\n";
        return ;
    }
    
    // before : 이전에 무엇을 추가했는가 (-1은 임시값)
    int before = -1;
    
    // 계속해서 순서대로 숫자를 저장
    for(int i = 1; i <= N; i++)
    {
        // 15654 N과 M (5) 의 차이점
        // → 방금 넣은 값을 기억한다
        // {num 배열에 없는 경우} + {방금 넣은 값과 다른 경우}
        if(!visited[i] && before != input[i])
        {
            // 1. num 배열에 있다고 표시
            // 2. num 배열에 input 배열의 숫자를 넣고
            // 3. 재귀
            // 4. 방금 넣은 값을 기억하고
            // 5. num 배열에 없다고 표시
            visited[i] = true;
            num[cnt + 1] = input[i];
            NM(cnt + 1);
            before = input[i];
            visited[i] = false;
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> M;
    
    // 숫자들을 입력 받고
    for(int n = 1; n <= N; n++)
        cin >> input[n];
    
    // 입력된 숫자들을 오름차순으로 정렬
    sort(input + 1, input + N + 1);
    
    // 처음에 num 배열에는 0개의 숫자가 저장되어 있으므로
    NM(0);
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 2/2] - [520 - 브루트 포스 (N과 M)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	15649	N과 M (1)	https://pirateturtle.tistory.com/243
2	15650	N과 M (2)	https://pirateturtle.tistory.com/244
3	15651	N과 M (3)	https://pirateturtle.tistory.com/245
4	15652	N과 M (4)	https://pirateturtle.tistory.com/246
5	15654	N과 M (5)	https://pirateturtle.tistory.com/247
6	15655	N과 M (6)	https://pirateturtle.tistory.com/248
7	15656	N과 M (7)	https://pirateturtle.tistory.com/249
8	15657	N과 M (8)	https://pirateturtle.tistory.com/250
9	15663	N과 M (9)	https://pirateturtle.tistory.com/251
10	15664	N과 M (10)	https://pirateturtle.tistory.com/252
11	15665	N과 M (11)	https://pirateturtle.tistory.com/253
12	15666	N과 M (12)	https://pirateturtle.tistory.com/254