[BOJ] C++ 15663: N과 M (9) - 중복 제거가 헷갈리는 백트래킹

15663번: N과 M (9)

예제 1                                                                                                                                                                                       

3 1
4 4 2

ans :
2
4

예제 2                                                                                                                                                                                       

4 2
9 7 9 1

ans :
1 7
1 9
7 1
7 9
9 1
9 7
9 9

 

예제 3                                                                                                                                                                                       

4 4
1 1 1 1

ans : 1 1 1 1

---

백트래킹에 대한 설명 없이 바로 풀이를 할 예정입니다. 기본 백트래킹 코드를 잘 모르거나 백트래킹이 익숙하지 않으면 아래 게시글을 꼭 읽어보길 바랍니다!!

[알고리즘] 백트래킹 - 재귀를 통한 구현과 응용 문제

---

다른 N과 M 시리즈들과는 다르게 난이도가 높아진 게 갑자기 느껴진다. 이번에는 풀이를 정성스레 떠올려야 할 것 같다. 우선 트리를 그려보면서 언제 중복을 제거해야 좋을지 생각해 보자.

말로 설명하려 하니 좀 꼬이는데, 같은 길이의 항에 대해(같은 값의 k에 대해) 이전에 구한 수열의 마지막 항과 현재 방문하려 하는 항이 같으면 중복이라는 뜻이다. 이 트리 그대로 구현해 주면 된다.

 

func(k+1)을 호출하기 전에 현재 항과 비교에 사용될 temp 값에 수열의 마지막 항을 넣는다. temp = arr[i] 부분이 되겠다. 그리고 func(k+1) 호출이 끝나면 호출 전의 i값에 대한 수열은 모두 구했을 것이고, 다음 for문에서 i번째 숫자를 방문하지 않았고 temp와 다르다면 다른 수열이다. if(! visited[i] && temp!= arr[i]) 부분이다. 만약 temp == arr[i] 라면 arr[i]가 이전 for문 단계에서 구한 수열의 마지막 항과 같으므로 현재 arr[i]를 부모로 하는 모든 자식들이 중복이므로 방문하지 않는다.

/** BackTracking 15663 N과 M (9) **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int arr[10];
int res[10];
bool visited[10];
int n, m;

void func(int k)
{
    if (k == m)
    {
        for (int i = 0; i < m; i++)
            cout << res[i] << ' ';
        cout << '\n';
        return;
    }
    int temp = 0;
    for (int i = 0; i < n; i++)
    {
        if (!visited[i] && temp != arr[i])
        {
            temp = arr[i];
            res[k] = arr[i];
            visited[i] = true;
            func(k + 1);
            visited[i] = false;
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> arr[i];
    sort(arr, arr + n);

    func(0);
}