chapter06 : 소풍

문제

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

예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.
(태연,제시카) (써니,티파니) (효연,유리)
(태연,제시카) (써니,유리) (효연,티파니)

입력

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

문제 회고

알고리즘 공부를하면서 문제를 정확하게 잘 이해하는게 정말 중요함을 절실히 느낀다..

지문의 핵심을 보자,
1) 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 
2) 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.
개인적으로 문제를 이해하는 코어 지문은 위의 두 문장이라 생각한다.

문제를 보고 예제 입력을 분석해보자. (상세 부분들은 숙지 했다는 전제하에...)
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
위와 같이 주어진다.

3은 테스트 케이스 개수이다. 여기서는 (2, 1), (4, 6), (6, 10) 이 될것이다.
예를 마지막 (6, 10)으로 설명하겠다.
(6, 10) 다음에 아래와 같은 숫자들이 쭉 들어온다.
0 1 0 2 1 2 1 3 1 4 2 3 2 4 3 4 3 5 4 5 
처음에는 위의 숫자가 뭘까 한참 고민했다... 이 시점에 입력 지문에서 "m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다" 이렇게 알려준다. 즉 위의 숫자들은 쌍이라는 것이다;;
(0 1) (0 2) (1 2) (1 3) (1 4) (2 3) (2 4) (3 4) (3 5) (4 5) 이런 모양으로 이해하면 될 것이다.
여기서 
0과 1은 친구이다.
0과 2도 친구다.
하지만
0과 3은 친구가 아님을 알 수 있다.

(0 1) (0 2) (1 2) (1 3) (1 4) (2 3) (2 4) (3 4) (3 5) (4 5) 
요것을 2차원 배열로 생각해보자.
0번과 친구 - 1, 2
1번과 친구 - 0, 2, 3, 4
2번과 친구 - 0, 1, 3, 4
3번과 친구 - 1, 2, 4, 5
4번과 친구 - 1, 2, 3, 5
5번과 친구 - 3, 4
이다.
이를 friendList[0][1] = true 라고도 표현할 수 있을 것이다.
또 서로 친구 라고 하였기 때문에
friendList[1][0] = true 이렇게 도 해줄 수 있을 것이다.

여기까지 이해를 했으면 그다음부터는 쉽게 풀어나갔다. 나머지는 단순 재귀를 통한 조건에 맞게 짝이 가능한 모든 조합을 구하면된다. 

코드

import java.util.*;
import java.io.*; 
 
 
public class Main { 
  
  static int N;
  static boolean[][] friendList; 
  
  
  // take[i] = i 번째 학생이 짝을 이미 찾앗으면 true, 아니면 false
  static int countPairings( boolean[] taken ) {
     
    int firstFree = -1;
    
    for ( int i = 0; i < N; ++i ) {
      if( !taken[i] ) {
        firstFree = i;
        break;
      }
    }
    
    if ( firstFree == -1 ) return 1;
    int ret = 0; 
    for ( int pairWith = firstFree + 1; pairWith < N; ++pairWith ) {
      if ( !taken[ pairWith ] && friendList[ firstFree ][ pairWith ] ) {
        taken[ firstFree ] = taken[ pairWith ] = true;
        ret += countPairings( taken );
        taken[ pairWith ] = taken[ firstFree ] = false;
      }
    }
    
    return ret;
  }
  
  // main  
  public static void main( String[] args ) throws Exception {
    
    // Please Enter Your Code Here 
    BufferedWriter bw  = new BufferedWriter( new OutputStreamWriter( System.out ) );
    BufferedReader br  = new BufferedReader( new InputStreamReader( System.in ) );
    StringTokenizer st = null;
    StringBuilder sb   = new StringBuilder();
    
    int C = Integer.parseInt( br.readLine() ); 
    while ( C --> 0 ) {
      
      friendList = new boolean[10][10];
      
      st = new StringTokenizer( br.readLine() );
      N  = Integer.parseInt( st.nextToken() );
      int M = Integer.parseInt( st.nextToken() );
      
      // 친구 관계를 설정해준다. 
      st = new StringTokenizer( br.readLine() );
      for ( int i = 0; i < M; ++i ) {
        int[] idx = new int[2];
        for ( int j = 0; j < 2; ++j ) {
          idx[j] = Integer.parseInt( st.nextToken() ); 
        } 
        friendList[ idx[0] ][ idx[1] ] = true;
        friendList[ idx[1] ][ idx[0] ] = true; 
      } 
      
      boolean[] taken = new boolean[10];
      int res = countPairings( taken );
      System.out.println( res );
      
    } 
     
    bw.flush();
    bw.close();
    br.close(); 
  }  
  
} 

다시 풀기

import java.util.*;
import java.io.*;  
 
 
public class Main { 
  
  static int N; 
  static boolean[] taken;
  static boolean[][] friendList;
  
  
  static int countPairings() { 
    
    // 짝을 찾아야될 인덱스를 구한다.
    int first = -1;
    for ( int i = 0; i < N; ++i ) {
      if ( !taken[i] ) {
        first = i; 
        break;
      }
    }
     
    // 기저조건 : 모든 친구가 짝이 이루어진 경우
    if ( first == -1 ) return 1;
    
    int ret = 0;
    for ( int pair = first + 1; pair < N; ++pair ) {
      // !taken[pair] : 이미 위에서 !taken[first]는 검증되었으니 안해도 된다.
      if ( !taken[pair] && friendList[first][pair] ) {
        taken[first] = taken[pair] = true;
        ret += countPairings();
        taken[first] = taken[pair] = false;
      }
       
    }
    
    return ret;
  }
  
  
  // main  
  public static void main( String[] args ) throws Exception {
    
    // Please Enter Your Code Here 
    BufferedWriter bw  = new BufferedWriter( new OutputStreamWriter( System.out ) );
    BufferedReader br  = new BufferedReader( new InputStreamReader( System.in ) );
    StringBuilder sb   = new StringBuilder();
    StringTokenizer st = null;
    
    int C = Integer.parseInt( br.readLine() );
    while ( C --> 0 ) {
      
      friendList = new boolean[10][10]; 
      st    = new StringTokenizer( br.readLine() );
      N     = Integer.parseInt( st.nextToken() );
      int M = Integer.parseInt( st.nextToken() );
      st    = new StringTokenizer( br.readLine() );
      
      for ( int i = 0; i < M; ++i ) {
        int[] idx = new int[2];
        for ( int j = 0; j < 2; ++j ) idx[j] = Integer.parseInt( st.nextToken() );
        friendList[ idx[0] ][ idx[1] ] = true;
        friendList[ idx[1] ][ idx[0] ] = true;
      }
      
      taken = new boolean[10];
      int res = countPairings();
      sb.append( res ).append( "\n" ); 
    }
    
    bw.write( sb.toString() );
    bw.flush();
    bw.close();
    br.close(); 
  }  
  
} 

 

 

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

algospot.com :: PICNIC