[C++] 백준 15654번 - N과 M(5) (백트래킹) 문제

#백준 15654번 N과 M(5)

 

 

백준 15654번 문제는 백트래킹 개념과 dfs 개념만 알고 있으면 쉽게 해결할 수 있는 문제이다.

바로 전에 N과 M(4)를 풀고와서 혼자 힘으로 해결할 수 있었다. 개꿀!

 

 

문제 링크

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

15654번: N과 M (5)

 

알고리즘

이 문제에 대한 자세한 플로우는 비슷한 문제인 N과 M(4)에 흐름을 자세히 설명해 생략하겠다.

https://rainycode.tistory.com/entry/C-%EB%B0%B1%EC%A4%80-15652%EB%B2%88-N%EA%B3%BC-M4-%EB%B0%B1%ED%8A%B8%EB%9E%98%ED%82%B9-%EB%AC%B8%EC%A0%9C-%ED%92%80%EC%9D%B4

[C++] 백준 15652번 - N과 M(4) (백트래킹) 문제 풀이

 

이 문제만의 특징은 중복을 해결하는 것이다. 그것은 dfs에서 흔히 사용하는 visited 배열을 사용해서 해결할 수 있다.

인덱스로 배열의 원소를 사용했는지 체크하면서 백트래킹을 거슬러 올라가면 문제를 해결할 수 있을 것이다.

 

코드

#include <iostream>
#include <algorithm>
#define MAX 8

using namespace std;

int N, M;
int arr[MAX];
int seq[MAX];
int visited[MAX];

void dfs(int num, int k){
    if(k==M){
        for(auto i = 0; i < M; i++){
            cout << seq[i] << ' ';
        }
        cout << '\n';
    }else{
        for(auto i = num; i < N; i++){
            if(visited[i]==1) continue;
            seq[k]=arr[i];
            visited[i]=1;
            dfs(num, k+1);
            visited[i]=0;
        }
    }
}

int main()
{
    cin >> N >> M;
    int k;
    for (auto i = 0; i < N; i++){
        cin >> k;
        arr[i]=k;
    }
    
    sort(arr, arr + N);
        
    dfs(0,0);
    return 0;
}

제출 결과

두 번만에 성공~ 슬슬 감이 좀 살아날지도..?