백준 15663번(N과 M (9)) 문제는 백트래킹 유형 이었다.
백준에서 제공하는 테스트 케이스를 모두 통과했지만 계속 틀렸다고 뜨길래 이것저것 고쳐보다가 어쩌다 통과를 했다. 근데 이게 왜 되지..?? 별다른 차이가 없어서 직접 트리구조를 그려보다가 드디어 발견을 했다..!
백준 질문검색 페이지에 2%에서 틀렸다고 하시는 분들이 많아서 글로 남겨보려고 한다.
2% 에서 틀렸던 코드다.
#include <iostream>
#include <algorithm>
using namespace std;
int lst[10], res[10];
bool pick[10];
int n, m;
void func(int k) {
if (k == m) {
for (int i = 0; i < m; i++)
cout << res[i] << ' ';
cout << '\n';
return ;
}
for (int i = 0; i < n; i++) {
if (!pick[i] && res[k] != lst[i]) {
res[k] = lst[i];
pick[i] = 1;
func(k + 1);
pick[i] = 0;
}
}
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> lst[i];
sort(lst, lst + n);
func(0);
}각각 1, 1, 1, 7, 9가 쓰여진 5장의 카드를 중복 없이 뽑는다고 했을 때
다음 사이클 때 같은 카드를 또 뽑기 싫어서 밑의 배열을 사용해 조건문으로 제외해 주었다.
bool pick[10]; // pick[i] = 1
if (!pick[i] && ...) {
...
}같은 숫자가 쓰여진 다른 카드를 뽑는다면 다음 사이클 때 같은 dfs를 반복하게 되므로 밑의 조건문을 사용해 제외해 주었다.
if (... && res[k] != lst[i]) {
... // res[k]는 k의 길이를 갖는 직전 사이클 수열의 마지막 항
}하지만 위의 조건문에는 눈치채지 못한 문제가 있었다.
func함수의 for문에 그 문제가 있었는데 지금부터 알아보자
for (int i = 0; i < n; i++) {
if (!pick[i] && res[k] != lst[i]) {
res[k] = lst[i];
pick[i] = 1;
func(k + 1);
pick[i] = 0;
}
}이랬던 코드가
int tmp = 0; // 이곳이 차이점!!!!!
for (int i = 0; i < n; i++) {
if (!pick[i] && tmp != lst[i]) { // 이곳도 !!!!!
res[k] = lst[i];
tmp = res[k]; // // 이곳도 !!!!!
pick[i] = 1;
func(k + 1);
pick[i] = 0;
}
}이렇게!!
처음에 코드를 짤 때는 이렇게 생각했다.
'길이(k)가 같은 직전 사이클 수열의 마지막 항과 비교해 같다면 이번 사이클의 dfs는 같은 값을 출력하게 되므로 제외해야지'
하지만 이런 생각은 다음과 같은 경우를 배제 했다.
길이(k) 앞 까지는 직전 사이클과 다른데 이번 사이클의 마지막 항이 직전 사이클의 마지막항과 같다면..?
말주변이 부족해서 나도 잘 이해가 안가니 예시를 봐보자 ㅎㅎ...
잘 봐보면 직전 사이클 수열인 7 9 1의 마지막 항이 1이고 따라서 res[k]의 값이 1이다.
다음 사이클로 넘어왔을 때 여전히 res[k]의 값이 유지되고 있으므로 수열 9 1 1의 선택이 불가능하다.
이처럼 트리의 줄기가 다를 경우에는 res[k]에 값이 채워져 있지 않다고 가정해야 한다.
이것을 나는 tmp라는 변수를 사용해 해당 줄기에서 res[k]값이 정해지면 그때 tmp를 res[k]로 바꿔주는 방법으로 처리했다.
int tmp = 0;그러므로 정답 코드는 이렇게!!
// N과 M (9)
#include <iostream>
#include <algorithm>
using namespace std;
int lst[10], res[10];
bool pick[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 tmp = 0; // 이곳이 차이점!!!!!
for (int i = 0; i < n; i++) {
if (!pick[i] && tmp != lst[i]) { // 이곳도 !!!!!
res[k] = lst[i];
tmp = res[k]; // // 이곳도 !!!!!
pick[i] = 1;
func(k + 1);
pick[i] = 0;
}
}
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++)
cin >> lst[i];
sort(lst, lst + n);
func(0);
}