PS

알고스팟 소풍

남마허 2020. 1. 9. 21:26

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

 

algospot.com :: PICNIC

소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다. 각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요

algospot.com

 

<접근방법>

n이 매우 작기 때문에 완전탐색으로 풀 수 있겠다고 생각했다.

단, 중복을 없애고 고르는 것이 관건이라고 생각했다. 그래서 처음에는 nC2를 n/2번 하면 되겠다고 생각했다. 그런데 구현도 못하겠고 답이 이상하다.

책에 나온 방법을 예시로 설명하면

n = 6이 일때,

(0, 1)(?, ?)(?, ?)/................../(1, 0)(?, ?)(?, ?)

(1, 0)이 나오기 전까지만 갯수를 세었다.

 

구현방법은 무조건 (순번이 빠른 사람, 순번이 느린 사람) 이렇게 고르게 만드는 것이다.

그러면 중복이 없이 카운팅을 할 수 있다.

 

 

 

 

<시간복잡도>

완전탐색이므로 최대 갯수를 세어보자.

열 명의 학생이 모두 친구인 경우가 그렇다.

9 * 7 * 5 * 3 * 1 = 945이다.

 

 

 

 

 

 

<코드>

#include <iostream>
#include <algorithm>
#include <memory.h>
using namespace std;

int tc, n, m;
int areFriend[10][10], visit[10];

int make() {
	int low = -1;
	for (int i = 0; i < n; i++) {
		if (visit[i] == 0) {
			low = i;
			break;
		}
	}
	if (low == -1) return 1;

	int res = 0;
	for(int i = low+1; i < n; i++){
		if (visit[i] == 1 || areFriend[low][i] == 0) continue;
		visit[low] = visit[i] = 1;
		//printf("c : %d %d\n", low, i);
		res += make();
		visit[low] = visit[i] = 0;
	}
	return res;
}


int main() {
	scanf("%d", &tc);

	while (tc--) {
		//초기화
		memset(visit, 0, sizeof(visit));
		memset(areFriend, 0, sizeof(areFriend));

		scanf("%d %d", &n, &m);
		for (int i = 0; i < m; i++) {
			int a, b;
			scanf("%d %d", &a, &b);
			areFriend[a][b] = 1;
			areFriend[b][a] = 1;
		}

		printf("%d\n", make());
	}


	return 0;
}

 

 

<느낀 점>

생각못한 접근방법이다. 외워둬야겠다.

반응형