[백준] 15663번 : N과 M (9)

문제

 

---

풀이

 

예제 입력 2에 대해 그냥 중복 상관없이 모든 수열을 사전순으로 출력하면

 

1 7

1 9

1 9

7 1

7 9

7 9

9 1

9 7

9 9

9 1

9 7

9 9

 

가 될 것이다. 여기서 중복을 제거해야 하는데 처음엔 아무리 머리를 굴려봐도 비효율적인 방법만 떠올랐다.

출력한 수열을 모두 저장해서 비교한다거나...각 숫자의 등장횟수를 세서 계산한다거나...

 

그러다가 백트래킹 과정을 그림으로 그려봐야겠다 싶었다.

 

현재 1을 선택한 상황에서 백트래킹으로 7을 선택했다. (1-7)

그리고 더 이상 고를 필요가 없으니 다시 1로 올라와서 9로 내려간다. 9가 선택된 상태이다. (1-9)

또다시 1로 올라와서 9를 선택하려고 보니 이전에 선택한 값과 같은 값이다. 이러면 탐색을 하지 않는 것이다.

 

9 1

9 7

9 9

가 반복되는 상황에도 적용할 수 있다.

 

9 1 / 9 7 / 9 9 를 모두 출력하고 더이상 탐색할 것이 없어 root인 0으로 돌아왔을 때 직전에 탐색한 노드는 root 바로 아래의 9이다.

이는 다음에 위치한 9와 같은 값이기 때문에 다음에 위치한 9는 탐색하지 않는다.

 

물론 이 과정이 가능하려면 수열이 정렬된 상태여야 한다.

---

소스코드

 

#include <iostream>
#include <algorithm>

using namespace std;

int input[8], arr[8];
int N, M;
bool visited[8];

void backtracking(int num) {
    if (num == M) { //출력
        for (int i = 0; i < M; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    int value = -1; //이전에 선택한 값 기억
    for (int i = 0; i < N; i++) {
        if (!visited[i] && (value != input[i])) { //방문 여부와 함께 이전 탐색 여부도 검사
            value = input[i];
            visited[i] = true; //visited 처리
            arr[num] = input[i];
            backtracking(num + 1);
            visited[i] = false; //unvisited 처리
        }
    }
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++)
        cin >> input[i];
    sort(input, input + N); //정렬
    backtracking(0);
}

다시 상위노드로 돌아와도 이전에 이 노드를 탐색했었다는 기억이 남아있어야 하기 때문에

unvisited 처리를 할 때도 value는 남겨둔다.