도입
한문제 푸는데 이렇게 시간이 오래 걸려서 큰일났네. 갈 길이 멀지만 차근차근 잘 익히면서 공부해야겠다.
아무 생각없이 들입다 코드 작성하고 시행착오로 풀이시간이 더 길어진다.
같은 문제를 풀려고 3개정도의 클래스를 만들었는데, 일부러 습관을 들이려고 하는 이 방식은 짰던 코드가 정답으로 통과되지 못할 경우 기존의 코드에 남아있는 나의 아이디어나 생각를 refresh 하려고 함이다.
기본 예제조차 통과하지 못했던 오답 코드를 다 풀고난 뒤 책의 뒷장을 넘겨보며 확인해보니 구체적인 구현 코드는 달랐지만 저자가 설명한 오답 사례로 그대로 있었다.
- 같은 학생 쌍을 두 번 짝지어 준다. 예를들어 (0,1)과 (1,0)을 따로 세고 있다.
- 다른 순서로 학생들을 짝지어 주는 것을 서로 다른 경우로 세고 있다. 예를 들어 (0,1)을 짝지은 후 (2,3)을 짝지어 주는 경우와 (2,3)을 짝지은 후 (0,1)을 짝짓는 경우를 따로 세고 있다.
나의 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class PICNIC_3 {
// https://algospot.com/judge/problem/read/PICNIC
static int C;
static int n;
static int m;
static boolean[] matched;
static int[][] mates;
static int count;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
C = Integer.parseInt(br.readLine().replaceAll(" ", ""));
while (C > 0) {
String line = br.readLine();
n = Integer.parseInt(line.split(" ")[0]);
m = Integer.parseInt(line.split(" ")[1]);
matched = new boolean[n];
mates = new int[m][2];
String mate = br.readLine();
String[] mateArr = mate.split(" ");
for (int i = 0; i < m; i++) {
mates[i][0] = Integer.parseInt(mateArr[2 * i]);
mates[i][1] = Integer.parseInt(mateArr[2 * i + 1]);
}
count = 0;
for (int i = 0; i < m; i++) {
mateCount(i, n);
}
sb.append(count).append("\n");
C --;
}
System.out.print(sb);
}
static void mateCount(int startIdx, int leftCount) {
int a = mates[startIdx][0];
int b = mates[startIdx][1];
matched[a] = true;
matched[b] = true;
leftCount -= 2;
if (leftCount == 0) {
matched[a] = false;
matched[b] = false;
count += 1;
return;
}
for (int i = startIdx; i < m; i++) {
int aa = mates[i][0];
int bb = mates[i][1];
if (!matched[aa] && !matched[bb])
mateCount(i, leftCount);
}
matched[a] = false;
matched[b] = false;
}
}해결 포인트
- m개의 짝의 수 중 한가지를 이용하여 두 명을 짝지을 경우에 모든 학생을 짝지을 수 있는 경우의 수를 찾고나면 이 한가지는 다시 볼 필요가 없다. 따라서 m개의 방법을 순환하며 앞에서부터 차례대로 하나씩 해결해나가면 된다.
- 하나의 방법으로 두 명의 학생을 짝짓고 재귀 호출이 끝나면 이 두 학생이 짝지어졌는지에 대한 boolean 값은 다시 false로 바꾸어 주어야 한다. 다른 방법으로 두 학생이 다시 짝지어질 수 있기 때문.
사실 2번은 처음부터 적용했던 포인트였고, 1번이 마지막에 정답으로 통과될 수 있었던 포인트인 것 같다.
mateCount 함수에서 leftCount를 인자로 넘길때, 기저 사례를 두 학생의 matched 값을 true로 바꾼 뒤 -2 계산해주는 방식이 상당히 거슬렸는데, 이로인해서 인자로 들어온 leftCount를 바로 기저 사례로 검사하여 함수를 종료하는 방식이 아닌, 현재 leftCount를 -2 해준 뒤, 기저사례일 경우 두 학생의 matched 값을 다시 false로 바꾸고 함수를 종료하는 방식이 아직도 좀 거슬린다.
이를 해결하기 위해서 최초 함수 호출 시 leftCount에 n-2를 전달하고, 재귀호출 시 leftCount 대신 leftCount - 2를 넘겨주는 방식을 적용해보았으나 이 또한 최초 호출시에는 아직 두 학생의 matched 값이 true가 아니기 때문에 상당히 거슬려서 결국 이와 같은 코드로 마무리 지었다.
책에서 설명하는 답안은 매칭 방식을 번호가 낮은 순으로 정렬한 뒤 재귀호출 함수에 직접 배열을 전달하며 앞에서부터 짝짓는 방식이었다. 같은 경우 카운트도 해결이되고, 다른 순서로 짝짓는 것 또한 해결한다.
막 복잡하게 생각하다 이제 겨우 풀어서 답안을 보면 생각보다 단순하고 훨씬 직관적이게 해결한 것을 보았던 경험은 예전에 백준에서 문제 마구 풀때도 겪었던 것 같다.
시도해본 것들
- mateArr 배열을 최초 input 을 받을때부터 int[] 자료형으로 받고 싶어서 아래와 같은 코드로 작성했다.
int[] mateArr = Arrays.stream(mate.split(" ")).mapToInt(Integer::parseInt).toArray();Algospot의 JAVA version 문제로 stream 코드에서 RTE가 발생했다. 굳이 기교를 부리다가...
- mates 배열을 boolean[][] 형태로 받아 학생 번호를 idx 삼아 두 학생이 짝이라면 true로 저장했는데, 이 때, 순서가 뒤집어져도 친구는 친구이니까 굳~~이 아래와 같이 input을 받았다.
mates[mateArr[2 * i]][mateArr[2 * i + 1]] = true;
mates[mateArr[2 * i + 1]][mateArr[2 * i]] = true;결과는 저자가 설명한 오답사례의 첫번째인 두번씩 세고 있었다.
- 재귀호출 함수에 결과값을 인자로 넘겨줬다.
public static void main(String[] args) {
...
count = mateCount(new boolean[n], n, 0);
...
}
static int mateCount(boolean[] grouped, int leftCount, int count) {
if (leftCount == 0)
return 1;
for (int i = 0; i < grouped.length; i++) {
if (grouped[i])
continue;
boolean[] friends = mates[i];
for (int j = 0; j < friends.length; j++) {
if (friends[j] && !grouped[j]) {
grouped[i] = grouped[j] = true;
count += mateCount(grouped, leftCount - 2, count);
grouped[i] = grouped[j] = false;
}
}
}
return count;
}
// grouped : n명의 학생이 찍지어졌는지 여부
// leftCount : n명의 학생 중 짝지어지지 않은 학생 수
// count : 얻고자하는 경우의 수예제 입력 2번째 경우 63같은 말도안되는 결과값이 나오길래 어이가 없어서 debugging해보니 count가 누적되고 있었다.
별 생각없이 문제풀고 코드 짜놓고 실행해버리면 이렇게 멘붕에 빠져버린다.
- 마지막은 나름 좀 신박하다고 생각했는데, 코드는 아래와 같다.
public static void main(String[] args) {
...
for (int i = 0; i < n; i++) {
allMatched += i;
}
for (int i = 0; i < m; i++) {
mates[i] = mateArr[2 * i] + mateArr[2 * i + 1];
}
...
mateCount(0, 0);
}위와 같이, 전부 매칭되었을 경우 학생들 번호의 총합을 구하고 (어차피 학생 번호는 0번부터 n-1버까지이니까), 각 짝짓는 m개의 케이스에 속한 학생의 번호를 더해서 배열에 저장했다.
static void mateCount(int matchedCnt, int curMatched) {
if (matchedCnt == n / 2) {
if (curMatched == allMatched)
count += 1;
return;
}
for (int i = 0; i < mates.length && !matched[i]; i++) {
matched[i] = true;
mateCount(matchedCnt + 1, curMatched + mates[i]);
matched[i] = false;
}
}
// matchedCnt : 짝지은 수
// curMatched : 현재까지 짝지은 학생들의 번호의 합그 다음 위와 같은 함수를 호출해서 matchedCnt가 학생 수의 절반(전부 짝지으면 n / 2개의 짝이 생기므로)이 되고, (중복 상관없이)짝지은 학생들의 번호를 전부 합해보니 전부 짝지었을때의 학생 번호의 합인 allMatched와 같으면 전부 제대로 짝지어졌다고 판단하고 경우의 수를 더하며 종료한다.
1. 학생의 번호 체번 방식이 달라지면 무슬모
2. **matchedCnt**가 학생 수의 절반이고 총 합이 **allmatched** 와 같아졌을때가 꼭 전부 제대로 매칭되었다고 보장할 수 없다.
예를 들어 학생 6명(0 1 2 3 4 5)일 경우 총합 15, 짝은 3짝이기만 하면 (0, 1), (4, 5), (0, 5) 이렇게 구성하면 조건을 만족한다.
3. 중복 카운트도 알 수 없다.역시 별 생각없이 풀고 코드 짜면 멘붕에 빠진다.
조금 더 신중하게 설계하고 코드 짜도록 노력해봐야겠다.
