[종만북][알고스팟] PICNIC(소풍) - 브루트포스(BruteForce) JAVA

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

algospot.com :: PICNIC

코드설명

브루트포스 문제입니다.

 

문제에서 유의해야할점은,

1. 중복된 재귀로 인해 중복적으로 친구를 짝짓는경우를 피해야합니다.

예시로, (보라돌이, 뚜비)와 (뚜비, 보라돌이)는 같은 경우입니다.

 

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다.

각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과

친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 친구쌍의 수가 n*(n-1)/2 인 이유는 nC2 조합 계산을 해보면 되겠습니다. N명의 친구 중 2개씩 뽑을 수 있는 조합의 최대 개수입니다.

 

잘못된 재귀 호출 코드를 개선합니다.

1. 같은 학생 쌍을 두번 짝지어줍니다. 예를 들어, (0,1)과 (1,0)을 따로 세고 있습니다.

2. 다른 순서로 학생들을 짝지어주는 것을 서로 다른 경우로 세고 있습니다. 예를 들어 (0, 1) 후에 (2, 3)을 짝지어주는 것과 (2,3) 후에 (0, 1)을 짝지어주는 것은 완전히 같은 방법인데 다른 경우로 세고 있습니다.

 

그러므로, 각 단계에서 남아있는 학생들 중 가장 번호가 빠른 학생의 짝을 찾아주도록 합니다.

즉, 항상 사전 순으로 가장 먼저 오는 답 하나만을 세도록 함으로써, 같은 방법인데 다른 경우로 세는 경우를 삭제해줍니다.

 

예시로 n = 4, 0 1 2 3 의 친구가 존재합니다. m = 6 으로, 모든 친구들이 서로 친구라고 가정합니다.(4C2 = 6, 6개로 모든 친구 조합을 만들 수 있음). 이떄 재귀로,  (0, 1)이 친구가 되었다고 합시다. 그리고 재귀가 다시 실행되어 (2, 3)이 친구가 됩니다. 4명이 모두 친구가 되어서 +1 시킵니다. 똑같이 (0, 2) (1, 3) 이 친구가 됩니다. 다시 (0, 3) (1, 2)가 친구가 됩니다. 여기서 함수 자체가 중단됩니다. 이유는, 가장 처음에 실행된 재귀함수가 딱 아직 친구가 없는 (0) 만 선택하고 친구로직을 수행한후에 종료되기 때문입니다.

for(int i=0; i<N;i++) {
    if(matched[i] == 0) {
        yetMatchedFriend = i;
        break;
    }
}

이를 통해 각 친구를 오직 한번만 선택하도록 함으로써 중복 자체가 발생하지 않습니다.

즉, 중복을 제거하기 위해 모든 재귀함수는 처음 기준으로 둘 친구를 딱 한명만 선택합니다. (그 친구와 연결된 친구들은 남은 친구들은 가능한 범위내에서 모두 선택합니다. 첫 기준으로 둘 친구를 강제함으로써 중복을 제거합니다.) 가장 먼저 만난 친구들을 모든 재귀함수가 딱 한번만 선택하고 다른 친구를 선택한 뒤 다음 재귀로 넘어감으로써, 중복이 발생하지 않습니다.

(친구 6명인경우, 모두 친구인 상태)로 판단해보시면 이해가 갈 것이라 생각합니다.

 

답의 수의 상한을 계산해봅니다. 

모든 답을 생성해가며 답의 수를 세는 재귀 호출 알고리즘은 답의 수에 정비례하는 시간이 걸립니다. 이 문제에서 가장 많은 답을 가질 수 있는 입력은 열명의 학생이 모두 서로 친구인 경우입니다. 이떄 가장 번호가 빠른 학생이 선택할 수 있는 짝은 9명이고, 그 다음 학생이 선택할 수 있는 짝은 7명, 5명, ... 으로 9 x 7 x 5 x 3 x 1 = 945 개의 친구가 가장 큰 답입니다.

코드

소풍 문제를 해결하는 잘못된 재귀 호출 코드입니다.

중복되는 연산 발생으로 더 많은 경우가 호출됩니다.

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	public static boolean[][] areFriends;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
			areFriends = new boolean[N][N];
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<M;i++) {
				int friendA = Integer.parseInt(st.nextToken()); int friendB = Integer.parseInt(st.nextToken());
				areFriends[friendA][friendB] = true; areFriends[friendB][friendA] = true;
			}
			int res = countPairings(new boolean[N]);
			System.out.println(res);
		}
		
	}
	
	public static int countPairings(boolean[] taken) {
		
		//기저 사례 : 모든 학생이 짝을 찾았으면 한가지 방법을 찾았으니 종료한다.
		boolean isFinished = true;
		for(int i=0;i<N;i++) if(!taken[i]) isFinished = false;
		if(isFinished) return 1;
		
		int ret = 0;
		//서로 친구인 두 학생을 찾아 짝을 지어준다.
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				if( !taken[i] && !taken[j] && areFriends[i][j] == true) {
					taken[i] = taken[j] = true;
					ret += countPairings(taken);
					taken[i] = taken[j] = false;
				}
			}
		}
		return ret;
	}
}

 

소풍 문제를 해결하는 재귀코드

package algorhythm;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	public static boolean[][] areFriends;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken());
			areFriends = new boolean[N][N];
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<M;i++) {
				int friendA = Integer.parseInt(st.nextToken()); int friendB = Integer.parseInt(st.nextToken());
				areFriends[friendA][friendB] = true; areFriends[friendB][friendA] = true;
			}
			int res = countPairings(new boolean[N]);
			System.out.println(res);
		}
		
	}
	
	//taken[i] = i번쨰 학생이 짝을 이미 찾았으면 true, 아니면 false
	public static int countPairings(boolean[] taken) {
		//남은 학생들 중 가장 번호가 빠른 학생을 찾는다.
		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 pairWith = firstFree + 1; pairWith < N; pairWith++) {
			if(!taken[firstFree] && !taken[pairWith] && areFriends[firstFree][pairWith]) {
				taken[firstFree] = taken[pairWith] = true;
				ret += countPairings(taken);
				taken[firstFree] = taken[pairWith] = false;
			}
		}
		return ret;
	}
}

 

소풍 문제를 해결하는 재귀코드 2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = Integer.MAX_VALUE;
	public static int[][] friendMatrix;
	public static int[] matched;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		
		while(C-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			matched = new int[N];
			friendMatrix = new int[N][N];
			
			st = new StringTokenizer(br.readLine());
			for(int i=0;i<M;i++) {
				int a = Integer.parseInt(st.nextToken());
				int b = Integer.parseInt(st.nextToken());
				friendMatrix[a][b] = friendMatrix[b][a] = 1;
			}
			System.out.println(makePair(0));
		}
		
		
	}
	public static int makePair(int level) {
		int yetMatchedFriend = -1;
		for(int i=0; i<N;i++) {
			if(matched[i] == 0) {
				yetMatchedFriend = i;
				break;
			}
		}
		if(yetMatchedFriend == -1) return 1;
		int ret = 0;
		for(int i=yetMatchedFriend + 1; i<N;i++) {
			if(friendMatrix[yetMatchedFriend][i] == 1 && friendMatrix[i][yetMatchedFriend] == 1 && matched[i] == 0) {
				matched[yetMatchedFriend] = matched[i] = 1;
				ret += makePair(level + 1);
				matched[yetMatchedFriend] = matched[i] = 0;
			}
		}
		
		return ret;
	}
	
}