재귀를 연습하기 위해서 풀어보았는데 너무 어려웠다..
기록용으로 남겨놓는다.
N과M 9번째 문제는 중복 제거가 핵심이다. 예를 들어
입력 케이스라 4 2 /9 7 9 1 라고 주어질 경우,
9가 두개 있다고 해서 1 9/ 1 9 로 두번 출력해서는 안된다.
첫 번째 방법
위의 예시를 들 경우 , 모든 경우의 수를 구하면 다음과 같은 것이다.
1 1
1 7
1 9
1 9
7 1
7 7
7 9
7 9
9 1
9 7
9 9
9 9
9 1
9 7
9 7
9 9
여기서 check를 이용해 방문한 것을 없애주면 결과는 다음과 같다.
1 7
1 9
1 9
7 1
7 9
7 9
9 1
9 7
9 9
9 1
9 7
9 9
이때 중복되는 경우를 제거해야 하는데 순서가 sort 된 경우, 전 경우의 조합과 지금 들어올 숫자를 비교해서 바꿀 수 있다. (if (res == a[i]) continue;)
여기서 드는 의문점은 왜 res를 따로 설정하여야 하냐 인데 그니까 temp[cnt] ==a[i] continue 로 왜 안하는지..
반례를 통해서 알 수 있다.
만약 3 3 / 3 3 5 일 경우
모든 경우는 다음과 같이 나온다.
3 3 3
3 3 3
3 3 5
3 3 3
3 3 3
3 3 5
3 5 3
3 5 3
3 5 5
3 3 3
3 3 3
3 3 5
3 3 3
3 3 3
3 3 5
3 5 3
3 5 3
3 5 5
5 3 3
5 3 3
5 3 5
5 3 3
5 3 3
5 3 5
5 5 3
5 5 3
5 5 5이를 check 로 방문했던것을 걸러주면,
3 3 5
3 3 5
3 5 3
3 3 5
3 5 3
5 3 3
5 3 3
이렇게 된다.
만약 res를 이용하여 템프 배열에 들어갈 숫자를 저장해 주지 않는다면 ,
3 3 5
3 5 3
의 결과를 갖는다.
3 5 3 에서 5 3 3 으로 갈때 depth 가 세번째의 트리에 temp[cnt]의 값이 3이기 때문에 continue 를 해주어서 정확한 결과가 나오지 않는다.
void solve (int cnt ) {
if (cnt == m) {
for (int i = 0; i < m; i++) {
cout << temp[i] << ' ';
}
cout << '\n';
return;
}
int res = -1;
for (int i = 0 ; i < n; i++) {
//cout <<"before: " <<cnt << temp[cnt] << '\n';
if (check[i] ==1) continue;
if (res == a[i]) continue;
res = a[i];
temp[cnt] = a[i];
//cout << "after : "<<cnt << temp[cnt] << '\n';
check[i] = 1;
solve(cnt + 1 );
check[i] = 0;
}
}두번째 방법
void solve(int num) {
if (num == m) {
for (int i = 0; i < m; i++) {
cout << temp[i] << ' ';
}cout << '\n';
return;
}
int cnt[10001] = { 0, };
for (int i = 0; i < n; i++) {
//if (check[i] == 1) continue;
if (check[i] == 1) continue;
if (cnt[a[i]] == 0) {
cnt[a[i]] += 1;
temp[num] = a[i];
check[i] = 1;;
solve(num + 1);
check[i] = 0;
}
}}
이와 같이 local 변수로 cnt 배열을 설정해준다. 동일한 숫자가쓰이지 않게 해주는 건 전역 변수인 check 로 조절해주고, cnt는 중복을 막기 위해서 이다. 즉 위의 예시에서는 check 는 1,1 이 들어오는걸 막고, cnt 는 9 가 두개 있는데 1 9, 1 9 로 들어오는 것을 막는다. 이는 로컬이기 때문에 가능한것!!
아직 dfs 개념을 잘 이해 못하겠다..
언젠가 나아지겠지..
