소풍 (ID : PICNIC)

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

algospot.com :: PICNIC

 

 

1. 첫 번째 시도

 

첫 번째 시도에서는 런타임 에러[RTE (nonzero return code)] 가 나왔다.

 

아래 소스의 43 라인에서 myFriends.get(studnet1) 의 값이 null 인지 체크해주지 않아서 발생한 문제였다. 문제의 원인을 찾았으니 null 체크 코드를 추가하고 다시 답안을 제출해보았다.

import java.util.*;

public class Main {
    public static int answer = 0;

    public static void main(String[] args) {
//        String filePath = "picnic/input.txt";
//        InputStream inputStream = Main.class.getClassLoader().getResourceAsStream(filePath);
//        Scanner scanner = new Scanner(inputStream);
        Scanner scanner = new Scanner(System.in);

        int caseCount = Integer.parseInt(scanner.nextLine());
        for (int c = 0; c < caseCount; c++) {
            String[] studentAndFriendCount = scanner.nextLine().trim().split(" ");
            int studentCount = Integer.parseInt(studentAndFriendCount[0]);
            int friendCount = Integer.parseInt(studentAndFriendCount[1]);

            Map<Integer, List<Integer>> myFriends = new HashMap<>();
            String[] friendPair = scanner.nextLine().trim().split(" ");

            for (int i = 0; i < friendCount * 2; i = i + 2) {
                int student1 = Integer.parseInt(friendPair[i]);
                int student2 = Integer.parseInt(friendPair[i + 1]);

                myFriends.computeIfAbsent(student1, k -> new ArrayList<>()).add(student2);
                myFriends.computeIfAbsent(student2, k -> new ArrayList<>()).add(student1);
            }

            // 친구 쌍 후보를 구한다.
            List<List<Integer>> friendCandidatePairs = new ArrayList<>();
            for (int i = 0; i < studentCount; i++) {
                for (int j = i + 1; j < studentCount; j++) {
                    friendCandidatePairs.add(Arrays.asList(i, j));
                }
            }

            // 친구 쌍 후보 중에서 실제로 친구인 경우만 추린다.
            List<List<Integer>> friendPairs = new ArrayList<>();
            for(List<Integer> friendCandidatePair : friendCandidatePairs) {
                int student1 = friendCandidatePair.get(0);
                int student2 = friendCandidatePair.get(1);

                if(myFriends.get(student1).contains(student2)) {
                    friendPairs.add(Arrays.asList(student1, student2));
                }
            }

            // 친구 쌍 후보 중에서 정답인 경우를 찾는다.
            answer = 0;
            Stack<List<Integer>> stack = new Stack<>();
            findCombination(friendPairs, stack, 0, studentCount, friendPairs.size());

            // 정답을 출력한다.
            System.out.println(answer);
        }
    }

    public static void findCombination(List<List<Integer>> friendPairs, Stack<List<Integer>> stack, int index, int studentCount, int friendPairsCount) {
        if (friendPairsCount <= index) {
            if(stack.size() == studentCount / 2) {
                if(isCombinationOk(stack, studentCount)) {
                    answer = answer + 1;
                }
            }
            return;
        }

        // 친구를 포함하지 않는 경우
        findCombination(friendPairs, stack, index + 1, studentCount, friendPairsCount);

        // 친구를 포함하는 경우
        stack.push(friendPairs.get(index));
        findCombination(friendPairs, stack, index + 1, studentCount, friendPairsCount);
        stack.pop();
    }

    public static boolean isCombinationOk(Stack<List<Integer>> stack, int studentCount) {
        boolean[] isSelected = new boolean[studentCount];

        for (List<Integer> friendPair : stack) {
            isSelected[friendPair.get(0)] = true;
            isSelected[friendPair.get(1)] = true;
        }

        for (int i = 0; i < studentCount; i++) {
            if (!isSelected[i]) {
                return false;
            }
        }

        return true;
    }
}

 

 

 

 

2. 두 번째 시도

 

이번에는 런타임 에러는 안났지만 시간초과가 나왔다. 수행 기준 시간을 초과한 것인데 어떤 부분을 개선해야 속도가 빨라질 수 있을지 고민이 필요하다.

 

import java.util.*;

public class Main {
    public static int answer = 0;

    public static void main(String[] args) {
//        String filePath = "picnic/input.txt";
//        InputStream inputStream = Main.class.getClassLoader().getResourceAsStream(filePath);
//        Scanner scanner = new Scanner(inputStream);
        Scanner scanner = new Scanner(System.in);

        int caseCount = Integer.parseInt(scanner.nextLine());
        for (int c = 0; c < caseCount; c++) {
            String[] studentAndFriendCount = scanner.nextLine().trim().split(" ");
            int studentCount = Integer.parseInt(studentAndFriendCount[0]);
            int friendCount = Integer.parseInt(studentAndFriendCount[1]);

            Map<Integer, List<Integer>> myFriends = new HashMap<>();
            String[] friendPair = scanner.nextLine().trim().split(" ");

            for (int i = 0; i < friendCount * 2; i = i + 2) {
                int student1 = Integer.parseInt(friendPair[i]);
                int student2 = Integer.parseInt(friendPair[i + 1]);

                myFriends.computeIfAbsent(student1, k -> new ArrayList<>()).add(student2);
                myFriends.computeIfAbsent(student2, k -> new ArrayList<>()).add(student1);
            }

            // 친구 쌍 후보를 구한다.
            List<List<Integer>> friendCandidatePairs = new ArrayList<>();
            for (int i = 0; i < studentCount; i++) {
                for (int j = i + 1; j < studentCount; j++) {
                    friendCandidatePairs.add(Arrays.asList(i, j));
                }
            }

            // 친구 쌍 후보 중에서 실제로 친구인 경우만 추린다.
            List<List<Integer>> friendPairs = new ArrayList<>();
            for(List<Integer> friendCandidatePair : friendCandidatePairs) {
                int student1 = friendCandidatePair.get(0);
                int student2 = friendCandidatePair.get(1);

                if(myFriends.get(student1) != null && myFriends.get(student1).contains(student2)) {
                    friendPairs.add(Arrays.asList(student1, student2));
                }
            }

            // 친구 쌍 후보 중에서 정답인 경우를 찾는다.
            answer = 0;
            Stack<List<Integer>> stack = new Stack<>();
            findCombination(friendPairs, stack, 0, studentCount, friendPairs.size());

            // 정답을 출력한다.
            System.out.println(answer);
        }
    }

    public static void findCombination(List<List<Integer>> friendPairs, Stack<List<Integer>> stack, int index, int studentCount, int friendPairsCount) {
        if (friendPairsCount <= index) {
            if(stack.size() == studentCount / 2) {
                if(isCombinationOk(stack, studentCount)) {
                    answer = answer + 1;
                }
            }
            return;
        }

        // 친구를 포함하지 않는 경우
        findCombination(friendPairs, stack, index + 1, studentCount, friendPairsCount);

        // 친구를 포함하는 경우
        stack.push(friendPairs.get(index));
        findCombination(friendPairs, stack, index + 1, studentCount, friendPairsCount);
        stack.pop();
    }

    public static boolean isCombinationOk(Stack<List<Integer>> stack, int studentCount) {
        boolean[] isSelected = new boolean[studentCount];

        for (List<Integer> friendPair : stack) {
            isSelected[friendPair.get(0)] = true;
            isSelected[friendPair.get(1)] = true;
        }

        for (int i = 0; i < studentCount; i++) {
            if (!isSelected[i]) {
                return false;
            }
        }

        return true;
    }
}

 

 

3. 세 번째 시도

 

개선점을 찾아내지 못해서 알고리즘 문제해결전략 책의 정답 코드를 봤다. 알고스팟에 제출한 정답 코드는 다음과 같다.

import java.util.*;

public class Main {
    public static int n = 0;
    public static int m = 0;
    public static boolean[][] areFriends = new boolean[10][10];
    public static boolean[] taken = new boolean[10];
    public static int answer = 0;

    public static void main(String[] args) {
//        String filePath = "picnic/input.txt";
//        InputStream inputStream = Main.class.getClassLoader().getResourceAsStream(filePath);
//        Scanner scanner = new Scanner(inputStream);
        Scanner scanner = new Scanner(System.in);

        int caseCount = Integer.parseInt(scanner.nextLine());
        for (int c = 0; c < caseCount; c++) {
            init();

            String[] nm = scanner.nextLine().trim().split(" ");
            n = Integer.parseInt(nm[0]);
            m = Integer.parseInt(nm[1]);

            String[] friendPair = scanner.nextLine().trim().split(" ");
            for (int i = 0; i < m * 2; i = i + 2) {
                int student1 = Integer.parseInt(friendPair[i]);
                int student2 = Integer.parseInt(friendPair[i + 1]);
                areFriends[student1][student2] = true;
                areFriends[student2][student1] = true;
            }

            // 정답을 출력한다.
            System.out.println(countPairings(taken));
        }
    }

    public static void init() {
        n = 0;
        m = 0;
        answer = 0;

        for (int i = 0; i < 10; i++) {
            Arrays.fill(areFriends[i], false);
        }
        Arrays.fill(taken, false);
    }

    public 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] && areFriends[firstFree][pairWith]) {
                taken[firstFree] = taken[pairWith] = true;
                ret += countPairings(taken);
                taken[firstFree] = taken[pairWith] = false;
            }
        }

        return ret;
    }
}

 

<참고>

https://minimalcode.tistory.com/149#4.%20%ED%92%80%EC%9D%B4%3A%20%EC%86%8C%ED%92%8D-1

[03 알고리즘 설계 패러다임] 6. 무식하게 풀기