BOJ - (Algospot) PICNIC 해결 전략 (C++)

Algospot - PICNIC

1. 문제 내용

  안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.

 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

(태연,제시카) (써니,티파니) (효연,유리)
(태연,제시카) (써니,유리) (효연,티파니)

2. 입력

  입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

3. 출력

  각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.

예제 입력
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

※ 내가 작성한 알고리즘

1) 조합을 찾고자 했으나, n명을 2명씩 조로 나누어 조합을 따지는 과정이 익숙치 않다고 느껴져, 차라리 n명의 순열을 쭉 나열하는 방식을 택함.

2) 입력받을때, 친구 정보를 기록하기 위해 10*10 크기의 2차원 불리언 배열 gganbu 도입.

3) 순열을 0번 인덱스부터 2단계씩 뛰어가면서 순회한다. 각 순회에서, i와 i+1번째 인덱스의 요소들이 서로 친구 사이인지 체크한다.

4) 조합 대신 순열을 택했으므로, 중복 처리가 필요하다. 이때는, 상황을 고정하는 센스를 취한다.

• students[i] < students[i + 1]인 순열들만 취한다. (중복 처리)
• students[i] > students[i - 2k]인 순열들만 취한다. (중복 처리)

~> 이 두 가지 조건을 곁들여 noflag 변수를 도입해 처리하면 이 문제를 해결할 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
// Algospot - PICNIC
using namespace std;

int wayCount;
vector<int> students;
bool gganbu[10][10];

void solve(int n) {
	bool noflag = false;

	for (int i = 0; i < n; i += 2) {
		if (!gganbu[students[i]][students[i + 1]]
			|| students[i] > students[i + 1])
			noflag = true;
	}
	if (!noflag) {
		for (int i = 2; i < n; i += 2) {
			if (students[i - 2] > students[i])
				noflag = true;
		}
	}

	if (!noflag)
		wayCount++;
}

int main(void) {
	int C, n, m, x, y, two = 1;
	long long cnt = 1;

	cin >> C;
	while (C--) {
		cin >> n >> m;

		for (int i = 0; i < n; i++)
			students.push_back(i);

		for (int i = 0; i < m; i++) {
			cin >> x >> y;
			gganbu[x][y] = true;
			gganbu[y][x] = true;
		}

		for (int i = n; i >= 1; i--) 
			cnt *= i;
		for (int i = 0; i < cnt; i++) {
			solve(n);
			next_permutation(students.begin(), students.end());
		}

		cout << wayCount << "\n";
		
		for (int i = 0; i < 10; i++) {
			for (int j = 0; j < 10; j++) {
				gganbu[i][j] = false;
			}
		}
		wayCount = 0; cnt = 1; two = 1; students.clear();
	}

	return 0;
}

※ 소감

  알고리즘 문제 해결 전략 세트의 첫 번째 문제인데, 솔직히 처음에 조금 얕봤다. 아무래도 첫 번째 문제다보니 쉬울 것이라 생각했다. 하지만 의외로 조합을 처리하는 기술을 내가 알고 있지 않다는 것이 충격적이었다. 그래서 생각보다 이 문제를 해결하는데 시간이 꽤 걸렸다. 솔직히 조금 부끄럽다. 모법 답안 코드를 분석해 조합을 처리하는 방법을 반드시 체득하겠다.

※ 모범 답안에서 주요한 Insight

for (int pairWith = firstFree + 1; pairWith < n; ++pairWith) {
    if(!taken[pairWith] && areFriends[firstFree][pairWith]) {
    	taken[..]=taken[..]=true;
        ret += ..
        taken .. = false;	// 후략
    }
}

  이 부분이 가장 중요한 부분이다. 처음에 내가 조합 방식을 포기하고 순열 방식을 택했던 이유가 바로 이 코드를 떠올리지 못해서였다. 내가 처음 시도했던 코드와의 유일하고도 매우 주요한 차이점은 바로, taken 배열의 도입 여부이다. visited 배열같은 역할인데, 아직 조합에 뽑히지 않은 정수들만 취급한다는 점이 주요한 특징이다.

단순히 firstFree보다 큰 정수들을 순차적으로 접근하는 것이 아니라, 크면서도 동시에 아직 뽑히지 않은 친구들을 택하는 것이다.

  이러한 접근방식은, 내가 작성한 답안 코드의 중복 처리 문이 필요 없게 하는 부분이다. 반드시 이 센스를 기억하도록 하자. 본인은 이를 "n명을 m명씩 뽑아 조합을 만들때 필요한 visited 배열 도입 센스"라고 명명하겠다(내 마음이다).