재귀호출
특정 조건에 따라 함수 자신을 반복 호출하여 문제의 답을 구하는 풀이 방법이다.
여기에서 중요한 건 두 가지이다.
- 기저사례
- 문제와 부분 문제
기저사례는 문제가 더이상 부분 문제로 쪼개질 수 없는 상황을 말한다. (무한루프에 빠지지 않도록 하기 위함도 있다.)
예를 들어, 팩토리얼을 재귀호출로 구현할 때, 재귀 함수로 받은 수가 1인 경우 바로 return을 하게 되는데, 숫자가 1일 때는 더 이상 부문 문제로 쪼개질 수가 없기 때문이다.
function factorial(n) {
// 기저 사례: n이 1이거나 그보다 작으면 1을 반환
if (n <= 1) return 1;
// 재귀 호출: n! = n * (n-1)!
return n * factorial(n - 1);
}
여기에서 문제란 큰 단위의 문제를 말한다.
팩토리얼로 예를 들면, n! = n * !(n - 1)가 문제가 되는데, 부분문제도 이와 같다.
즉, 재귀 호출은 문제를 더 작은 부분 문제로 나누어 해결한다.
큰 문제를 작은 문제로 쪼개면서 결국 기저 사례에 도달하게 된다.
예를 들어, n!를 계산하는 문제는 n * (n - 1)!로 표현되며, 이 n - 1에 대해 다시 팩토리얼을 구하는 문제로 쪼개진다. 이렇게 반복적으로 문제를 쪼개다 보면 결국 1!처럼 더 이상 쪼갤 수 없는 기저 사례에 도달하게 된다.
소풍 문제
문제
안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.
각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.
(태연,제시카) (써니,티파니) (효연,유리)
(태연,제시카) (써니,유리) (효연,티파니)
입력
입력의 첫 줄에는 테스트 케이스의 수 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
const fs = require("fs");
const data = fs.readFileSync("./test.txt", "utf8");
const input = data.split("\r\n");
let tc = input[0];
let curTc = 1;
let n, m, graph;
while (tc--) {
[n, m] = input[curTc++].split(" ").map(Number);
graph = Array.from(new Array(n), (v) => (v = new Array(n).fill(false)));
const friends = input[curTc++].split(" ").map(Number);
for (let i = 0; i < friends.length; i += 2) {
graph[friends[i]][friends[i + 1]] = true;
graph[friends[i + 1]][friends[i]] = true;
}
console.log(picnic(new Array(n).fill(false), 0, -1));
}
function picnic(friends, curFriends, curI) {
if (curFriends === n / 2) return 1;
let ret = 0;
for (let i = curI + 1; i < n; i++) {
if (friends[i]) continue;
for (let j = i + 1; j < n; j++) {
if (friends[j] || !graph[i][j]) continue;
friends[i] = friends[j] = true;
ret += picnic(friends, curFriends + 1, i);
friends[i] = friends[j] = false;
}
}
return ret;
}
문제 풀이
이 문제의 기저사례는 더 이상 모든 짝이 완성되었을 때이다.
모든 학생이 짝을 이루었을 때 기저 사례에 도달하며, 이 경우 가능한 한 가지 짝짓기 방법으로 간주하고 1을 반환한다
문제는 a와 b를 중복없이 짝 지어주는 것이다.
중복없이 짝을 지어줄 때 중요한 건, 항상 첫 번째 반복문의 인덱스보다 두 번째 반복문의 인덱스가 커야한다는 것이다. (0,1), (1,0) 만약 왼쪽에 위치한 수가 오른쪽 수보다 크다면 이 경우는 이전에 나온 반복문에서 이미 처리가 된 중복 경우의 수이기 때문이다.
모든 학생을 일렬로 세웠을 때, 학생 i가 이미 짝을 지은 상태라면, 그 이후 학생 j와의 새로운 짝짓기를 시도하는 방법으로 중복을 제거한다
중복을 제거할 때는 현재 짝을 이룬 학생은 별도 기록해 놨다가 남은 친구들의 짝을 지어줄 때 확인해서 한 사람이 두 명 이상의 친구와 짝이 되지 않도록 해야한다.(3, 5), (4, 5)
구체적인 구현 과정은 다음과 같다.
- 아직 짝이 없는 첫 번째 학생을 찾고, 이 학생과 짝이 될 수 있는 모든 학생을 차례로 시도합니다.
- 짝이 가능한 경우 두 학생을 짝지은 상태로 표시한 후, 나머지 학생들의 짝짓기 문제를 재귀적으로 해결합니다.
- 모든 짝이 완성되면 1을 반환하고, 그렇지 않으면 다른 짝짓기를 시도합니다.
