Algorithm/알고리즘 문제해결전략
소풍 (ID : PICNIC)
_su_min
2025. 2. 16. 14:10
https://www.algospot.com/judge/problem/read/PICNIC
algospot.com :: PICNIC
소풍 문제 정보 문제 안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로
www.algospot.com
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. 무식하게 풀기
1. 도입 프로그래밍 대회에서 대부분의 사람들이 가장 많이 하는 실수는 쉬운 문제를 어렵게 푸는 것입니다. 공부를 열심히 할수록 복잡하지만 우아한 답안을 만들고 싶은 마음이 커지기 마련
minimalcode.tistory.com