예제: 소풍
문제
안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.
- (태연,제시카) (써니,티파니) (효연,유리)
- (태연,제시카) (써니,유리) (효연,티파니)
입력
입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.출력
각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.예제 입력
3 2 1 0 1 4 6 0 1 1 2 2 3 3 0 0 2 1 3 6 10 0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5예제 출력
1 3 4풀이
이상하게 헤맸던 브루트포스 문제이다.
이유는, 함수를 처음에 paring(int idx)로 idx번 학생이 구할 수 있는 짝의 수로 함수를 구성하려고 했기 때문이다. 물론 할 수 있겠지만, idx 번째와 몇 번째 학생이 짝이 될지 알 수 없기 때문에, 이렇게 하면 로직이 쓸데없이 복잡해져 헤맸다.
헤매다가 어차피 브루트포스겠다, 입력 최대 수도 적겠다 아직 짝을 찾지 못한 학생을 그냥 for문으로 찾았다. 반복문으로 모든 경우의 수를 탐색하며 짝을 구성할 수 있는 수를 찾아주는 문제였다.
전체적인 소스코드는 아래와 같다.
소스 코드
#include<iostream>
#include<cstring>
using namespace std;
int n, m;
int isFriend[10][10];
int paired[10];
int paring() {
int idx = -1;
for (int i = 0; i < n; i++) {
if (paired[i] == -1) {
idx = i;
break;
}
}
if (idx == -1) return 1;
int res = 0;
for (int i = idx + 1; i < n; i++) {
if (paired[i] == -1 && isFriend[idx][i] == 1) {
paired[idx] = 1;
paired[i] = 1;
res += paring();
paired[idx] = -1;
paired[i] = -1;
}
}
return res;
}
int main() {
int testCase;
cin >> testCase;
for (int tc = 0; tc < testCase; tc++) {
cin >> n >> m;
memset(isFriend, -1, sizeof(isFriend));
memset(paired, -1, sizeof(paired));
for (int i = 0; i < m; i++) {
int y, x;
cin >> y >> x;
isFriend[y][x] = 1;
isFriend[x][y] = 1;
}
cout << paring() << endl;
}
return 0;
}풀이 후기
알고리즘 문제해결전략과 비슷해보이는 이유는 필자는 함수 처음에 isFinish()로 반복문을 한번 돈 후 모든 학생이 짝을 찾았으면 1을 리턴하는 형태였는데, 풀이처럼 짝을 찾지 못한 학생을 찾았을 경우 이를 감지하여 return 1을 하는 부분이 좋아보였다😅. 문제를 하루에 많이 풀어야하는데..
