[문제][알고스팟] PICNIC

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • PICNIC
  • 1000ms
  • 65536kb
  • 9057
  • 3864 (42%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

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

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

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

입력

입력의 첫 줄에는 테스트 케이스의 수 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

---

사람마다 공부하는 스타일이 있겠지만, 나는 무작정 많이 푼다고 느는 스타일은 아닌것같다..
요령보단 정석대로 꾸준히 나가는게 중요하다는 생각이 들었고, 기본으로 돌아가자는 마음에 기초적인 문제를 풀어봤다. 

PICNIC은 재귀를 사용하여 '무작정 풀어보기'로 풀 수 있다.

하지만 역시 기초적인 문제임에도 쉽게 풀리진 않았다. 
자료구조를 어떻게 해야할지, 심지어 재귀를 써야할지 말아야할지도 빠른 판단지 들지 않는걸 보면 기본이 부족한건 맞다 싶다.

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Picnic {
	
	public static int N,M;
	public static boolean friend[][];
	public static boolean align[];
	public static int count;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		System.setIn(new FileInputStream("D:///sample_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine().trim());
		for(int tc=1; tc<=T; tc++){
			StringTokenizer st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());
			
			align = new boolean[N];
			friend = new boolean[N][N];
			count = 0;
			
			st = new StringTokenizer(br.readLine());
			for(int i=0; i<M; i++){
				int one = Integer.parseInt(st.nextToken());
				int another = Integer.parseInt(st.nextToken());
				friend[one][another] = true;
				friend[another][one] = true;
			}
			
			count = findFriend();
			
			bw.flush();
			bw.write(count + "\n");
			
			
		}
		bw.close();

	}
	
	public static int findFriend(){
		int ret = 0;
		
		int firstFree = -1;
		for(int i=0; i<N; i++){
			if(!align[i]){
				firstFree = i;
				break;
			}
		}
		
		// 남은애가 없을때		
		if(firstFree == -1){
			return 1;
		}
			
		for(int j=firstFree+1; j<N; j++){
			
			// 둘다 할당이 안되어있고, 친구일 경우
			if(!align[j] && friend[firstFree][j]){
				align[firstFree] = align[j] = true;
				ret += findFriend();
//				count +=  findFriend();
				align[firstFree] = align[j] = false;
			}
		}
		
		return ret;
		
	}

}

짝으로 매칭되었는지 여부를 저장할 배열, 친구인지를 판단할 2차원 배열을 만든 후
재귀를 돌면서 아직 매칭이 안되었으면서 && 친구인경우 매칭여부를 true로 전환한다.

간단하지만 함정이 있다면
(1,2) 와 (2,1)을 중복으로 세는 경우,
(1,2), (3,4) 와 (3,4), (1,2)를 중복으로 세는 경우를 제외해야 한다.

매칭이 아직 안된 친구들 중에서 가장 앞번호의 친구를 기준으로 찾으면 중복을 제거할 수 있다.

---

* 재귀함수 내부에 count += findFriend(); 구문이 주석처리 되어있다.
처음에 정적변수 count에 리턴값을 합산하는 방식으로 구현하고자 했지만,
이상하게도 내부에서 count가 1이 된 후 부모 함수에서 count(1) 과 리턴값 0이 더해지면서 count가 0이 되는 현상이 생겼다.
왜그런지 아직 모르겠지만, 정적변수의 메모리 참조 문제가 아닐까 싶다.
원인을 찾아서 알아두어야 할 필요가 있어 보인다.