알고스팟__소풍

https://www.algospot.com/judge/problem/read/PICNIC

algospot.com :: PICNIC

풀이방법

 

첫번째 풀이

 

처음 생각한 풀이는 나올수 있는 순열을 모두 구해서 하나하나 세는 방법이었다.

하지만, 이 문제는 그렇게만 풀면 답이 다르게 나올수 있다. 왜냐하면

(철수, 영희)와 (민수, 미희)로 묶였을때를 찾는다고 해보자. 이때

 

(철수, 영희)와 (민수, 미희)뿐만이 아니라

(영희, 철수)와 (민수, 미희)

(영희, 철수)와 (미희, 민수)

(민수, 미희)와 (영희, 철수) 

.....

여러번의 똑같은 경우를 센다.

 

첫번째 풀이의 답이 오답이긴 하지만 증가하는 법칙이 정해져있어 그걸 이용해서 풀어보기도 했지만

전체 순열을 도는 점 때문에 시간초과가 난것 같다.

 

두번째 풀이

이건 종만북의 풀이다.

위의 경우처럼 중복으로 세는 경우를 해결하기위해 항상 특정 형태를 갖는 답만을 세는것이다.

이게 무슨소리냐면

(2, 3) (0, 1) 이나 (1, 0) (2, 3)의 경우는 세지않지만 (0, 1) (2, 3)처럼 짝이되는 맨앞의 수가 오름차순인 경우만 세는것이다.

 

설명이 부족할수도 있으니 예를 하나 들겠다.

ex) (0, 3) (2, 4) 이런 경우와 실질적으로 똑같은 경우는 아까 예를 들었던것 같이

(3, 0) (2, 4) , (2, 4) (0, 3) ... 등등 여러가지 경우가 나올수있다.

 

이때 (0, 3) (2, 4) 와 같이 짝이 되는 수의 가장 앞글자가 오름차순인 경우만 센다면 중복으로 세는 경우를 방지할수 있을것이다.

 

연산은 9 x 7 x 5 x 3 x1 x c(50) = 47,250 걸린다.

 

---

전체코드

#include <iostream>
#include <cstring>
using namespace std;

int n, m;
int areFreinds[12][12];

int countParings(bool taken[10])
{
	int firstFree = -1;
	//아직 짝이 되지않은 애들중에 제일 먼저인애 고르기
	for (int i = 0; i < n; i++)
	{
		if (taken[i] == false)
		{
			firstFree = i;
			break;
		}
	}

	//모든학생이 다 짝을 찾았으면 끝
	if (firstFree == -1)
		return 1;

	int ret = 0;

	//짝할 친구찾기
	for (int pairFriend = 0; pairFriend < n; pairFriend++)
	{
		if (taken[pairFriend] == true)
			continue;
		if (pairFriend == firstFree)
			continue;
		if (areFreinds[firstFree][pairFriend] == 1)
		{
			taken[firstFree] = taken[pairFriend] = true;
			ret += countParings(taken);
			taken[firstFree] = taken[pairFriend] = false;
		}
	}
	return ret;
}

void areFriendClear()
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			areFreinds[i][j] = 0;
}

int main()
{
	int c;
	cin >> c;
	for (int i = 0; i < c; i++)
	{
		cin >> n >> m;
		int f1, f2;
		for (int j = 0; j < m; j++)
		{
			cin >> f1 >> f2;
			areFreinds[f1][f2] = areFreinds[f2][f1] = 1;
		}

		//ㄱㄱ
		bool taken[10];
		memset(taken, false, 10);
		cout << countParings(taken) << endl;
		areFriendClear();
	}
	return 0;
}

---

후기

종만북 2권부터하다가 강결합 컴포넌트? 그 부분에서 멘탈이 심하게 나가서 한동안 책을 펴지 않았었다.

하지만 몇일전부터 실력에 문제가 있다는걸 다시한번 깨닫고 이번에는 1권부터 다시 보고있는데, 내가 짠 코드와 책의 코드가 너무 수준차이가 나서 조금 슬프다.ㅠ