[알고스팟] PICNIC - java

문제 정보

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

문제

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

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

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

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

---

문제는 심플하다

문제조차 이해하기 조금 어렵긴 햇지만 ㅎ;;

처음에 짯을때는 틀린줄알고 다른방법을 시도햇는데

알고보니 그답이 맞더라 

근데또 알고보니 br을 scanner로 바꿔주니 더 빠르더라.. 둘다 정답 뜨더랑...

bufferedReader보다 Scanner가 원래 더 느린데

이경우에는 Integer만 있어서

Parsing하는 과정에서 메모리를 많이 잡아먹는거같았다.

아래는 정석 풀이이다.

쓸데없는 내용이 조금 들어가있다. 

간단한 로직은 풀이 확인을 디버깅보다는 print하는 편이다. 사이클 여러개를 비교하기 땜시

---

최종본

package algoSpot.PICNIC;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

/**
 * Created by eunbi on 2018-02-05.
 * /
public class PICNIC_EB_list {
    public static StringBuilder sb = new StringBuilder();
    public static Scanner sc = new Scanner(System.in);

    public static int C;
    public static int count;
    public static int N;
    public static int M;
    public static boolean[][] freindsMap;


    public static void main(String[] args)  throws Exception{

        //Test Case
        C=sc.nextInt();
        for(int i=0;i<C;i++) {
            solve();
        }
        System.out.println(sb.toString());
        sc.close();
    }

    public static void solve()  throws Exception{

        // N, M 설정
        N = sc.nextInt();
        M = sc.nextInt();

        
        //초기화
        count =0;
        boolean[] checkList = new boolean[N];
        for (int i = 0; i < N; i++) {
            checkList[i] = false;
        }
        initMap();

        // input값을 이차원 배열에 삽입
        for (int i = 0; i < M; i ++) {

            freindsMap[sc.nextInt()][sc.nextInt()]  = true;
        }


        //해당 함수 호출
        picnic(checkList);
        
        //sb 에 결과 저장
        sb.append(count).append("\n");

//        System.out.println(sb.toString());
    }
    public static void print() {
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                System.out.print(freindsMap[i][j] + " ");

            }
            System.out.println();
        }
    }

    public static void picnic(boolean[] checkList) {
        //다음 n, 즉 false를 찾는다.
        int n=0;
        while (n<N&&checkList[n]){
            n++;
        }
        //모두 true일 때 : 기저, return
        if(n==N) {
            count++;
            return;
        }

        //n에 해당하는 친구 리스트 설정
        boolean[] isfriend = freindsMap[n];
        // 친구인지 검사
        for(int i=0;i<N;i++){
            // 친구이면서, 짝이 없는 아이
            if(isfriend[i] && !checkList[i]){
/*                boolean[] tempck = checkList.clone();

                tempck[i] = true;
                tempck[n] = true;*/
       
                checkList[i] = checkList[n] = true;
                picnic(checkList);
                checkList[i] = checkList[n] = false;
            }
        }

    }

    public static void initMap() {
        freindsMap = new boolean[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                freindsMap[i][j] = false;

            }
        }
    }


}

다른시도

노드라는 객체를 만들어서, false인것끼리 객체를 묶는 형식이다.

객체가 N/2개 묶이면 return

주의해야 할 점은

순서가 뒤바뀌는 경우가 생기는데

팩토리얼을 구해서 나누어주면 된다.

이것도 sc로 바꾸니까 정답처리 나왓다. 

왜 고생햇지

함수의 result값은 테스트를 위해 출력하는 값이다. 실제 코드는 지우면 된다.

package algoSpot.PICNIC;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by eunbi on 2018-02-05.
 */
public class PICNIC_EB_node {
    public static StringBuilder sb = new StringBuilder();
    public static Scanner sc = new Scanner(System.in);
    public static int C;
    public static int count=0;
    public static int N;
    public static int M;
    //public static int[][] freindsMap;

    public static List<Node> nodeList = new ArrayList<Node>();

    public static void main(String[] args)  throws Exception{
        C=sc.nextInt();
        for(int i=0;i<C;i++) {
            solve();
        }
        System.out.println(sb.toString());
        sc.close();
    }

    public static void solve() throws Exception {
        N = sc.nextInt();
        M = sc.nextInt();

        nodeList = new ArrayList<Node>();
        count = 0;
        boolean[] checkList = new boolean[N+1];
        for (int i = 0; i < N; i++) {
            checkList[i] = false;
        }

        for (int i = 0; i < M; i ++) {

            nodeList.add(new Node(sc.nextInt(), sc.nextInt()));
        }


        System.out.println(nodeList);
        for (Node node : nodeList) {
            boolean[] tempck = checkList.clone();

            tempck[node.a] = true;
            tempck[node.b] = true;
            picnic(tempck,  1, node.toString());
        }

        int divid =combination();
        //int divid = (int)Math.pow(2,N/2);
        sb.append(count / divid).append("\n");
//        System.out.println(count +"/"+ divid);
    }

    public static void picnic(boolean[] checkList,  int num, String result) throws Exception{

        // 쌍을 모두 찾음
        if(num == N/2){
            System.out.println(result);
            count++;
            return;
        }
        for(int i=0;num<N/2&&i<nodeList.size();i++){
            Node node = nodeList.get(i);
            if(!checkList[node.a] &&!checkList[node.b]){
                boolean[] tempck = checkList.clone();

                tempck[node.a] = true;
                tempck[node.b] = true;

                picnic(tempck,  num+1 ,result+node);
            }

        }


    }

    public static int combination(){
        int result=1;
        for(int i=1;i<=N/2;i++){
            result *= i;
        }
        return result;
    }
    public static class Node {
        int a;
        int b;

        public Node(int a, int b) {
            this.a = a;
            this.b = b;

        }

        @Override
        public String toString() {
            return "(" +
                    a +
                    ", " + b +
                    ')';
        }
    }
}