1. 문제 설정 확인
모든 학생들에게 짝을 하나씩 만들어줘야 한다.
2. 문제 풀이
저번에 다뤘던 BOGGLE GAME 보다도 더 쉬운 문제다. 하지만 약간 Tricky 한 점이, 바로 중복의 카운트다. 재귀함수를 호출하면서 어떻게 중복을 카운트 하지 않을 것인가?
예를 들어, 중복을 제거하지 않는다면 (0, 1), (1, 0)을 두 번씩이나 카운트 하게 된다. 여기서 알고리즘을 처음 접하는 분들이라면 으례
엥 ? 그거 그냥 result 구한 다음 2로 나눠주면 되지 않을까요?
라는.. 달콤한 유혹에 빠지기 쉽지만, 당연히 그렇게 간단하지 않다. 왜냐하면, 단순히 (0, 1) (1, 0)의 순서쌍을 두 번 세는것이 아닌, 짝을 짓는 순서 까지 무시해버린다. 예를 들자면,
(1, 0) (2, 3) (4, 5)로 짝지은것과 (2, 3) (1, 0) (4, 5)로 짝지은것을 다른 경우로 생각한다는 말이다.
그렇다면 이런 중복 제거를 어떻게 구현할 수 있을까?
간단하다. 번호가 빠른 사람들 먼저 짝 지어주면 된다. 오해하면 안 되는게, 번호가 빠른 사람들을 우선적으로 짝 지어주는 것이지, 번호가 빠른 사람들만 짝 짓고 (마치 정렬처럼) 떙이 아니다. 백트래킹은 백트래킹대로 해서, 모든 경우의 수를 구하되, 중복되는 경우에는 번호가 가장 빠른 경우의 순서쌍만 카운트하겠다는 뜻이다.
(1, 0) (2, 3) (4, 5)로 짝지은것과 (2, 3) (1, 0) (4, 5)로 짝지은것것 중, 번호가 더 빠른 첫 번째의 것만 카운트해주면 된다.
코드도 어렵지 않다.
3. 해답 코드
#include <iostream>
#include <vector>
using namespace std;
int solution(vector<vector<bool>> student, vector<bool> &isTaken, int length) {
int firstFree = -1;
for (int i = 0; i < length; i++){
if(!isTaken[i]){
firstFree = i;
break;
}
}
if (firstFree == -1) {
return 1;
}
int ret = 0;
for(int pairWith = firstFree + 1; pairWith < length; pairWith++){
if(!isTaken[pairWith] && student[firstFree][pairWith]) {
isTaken[firstFree] = isTaken[pairWith] = true;
ret += solution(student, isTaken, length);
isTaken[firstFree] = isTaken[pairWith] = false;
}
}
return ret;
}
int main () {
int n;
cin >> n;
for(int i=0; i< n; i++){
int a, b;
cin >> a >> b;
vector<vector<bool>> student;
vector<bool> isTaken(a, false);
vector<bool> arr(a, false);
for(int j = 0; j < a; j++){
student.push_back(arr);
}
for(int j = 0; j < b; j++){
int x, y;
cin >> x >> y;
student[x][y] = true;
student[y][x] = true;
}
cout << solution(student, isTaken, a) << endl;
}
}
이런식으로, 그냥 백트래킹을 구현하되 중복을 제거해주기 위해 남은 사람들 중 가장 빠른 사람의 짝을 찾아준다.
문제과 별개로… 어제 C++ 배열을 다뤄보고, 꽤나 멘붕이 왔다. (…) 익숙해지면 괜찮겠지만, 아직까지는 솔직히 감이 잘 안 잡힌다. 하지만 vector의 경우엔 다르다. 꽤나 직관적이고, 마치 파이썬의 배열 (물론 파이썬보단 다루긴 훨씬 어렵지만) 다루듯 다룰 수 있어, 일단은 vector를 사용하려고 한다. 다음 포스트로는 vector와 깡 배열의 차이, 또 접근 방법의 차이 등등을 정리해서 올려보려고 한다.
Source
- 종만북, 2022.07.22
- CLion