소풍
in Computer Science on Algorithm
소풍
각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지을 수 있는 방법의 수를 계산하는 프로그램을 작성하시오. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 가정합니다.
사실 위의 문제는 백준, 프로그래머스 문제가 아닌, 알고리즘 종만북이라는 책의 내용을 토대로 문제를 풀이하게 되었다. 계속해서 문제를 양치기 하는 것보다 문제를 어떻게 해결하는가에 중심을 둬서 배우고 싶어서 책을 꺼냈다.
접근
책에서는 이 문제를 모든 가능한 조합의 수를 계산하는 방법은 완전 탐색과 재귀호출을 이용하여 문제를 해결하였다. 재귀호출로 문제를 풀면 고려해야 할 것들이 백트래킹과, 기저사례이다. 사실 위의 두 지식도 알고만 있지 제대로 적절하게 활용하는 법을 자세히는 알지 못해서 이번기회에 제대로 배워볼까 한다. 우선 문제의 풀이는 짝을 찾지 못한 학생들의 명단이 주어질 때 친구끼리 둘씩 짝짓는 경우의 수를 계산하라가 된다. 명단에서 서로 친구인 두 학생을 찾아 이들을 짝지어 주고나면 남는 학생들을 짝지어 주는 문제도 원래 문제와 같은 형태가 된다.
코드
#include<bits/stdc++.h>
using namespace std;
int n,m;
bool areFriends[10][10];
int countPairings(bool taken[10]){
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;
}
int main(){
cin >> n;
cin >> m;
fill(&areFriends[0][0], &areFriends[0][0] + 10 * 10, false);
for(int i = 0; i < m; i++){
int a,b;
cin >> a >> b;
areFriends[a][b] = true;
areFriends[b][a] = true;
}
bool taken[10] = {false};
cout << countPairings(taken) << '\n';
return 0;
}
기저사례 종료조건
기저사례로 재귀호출을 종료시킬 때 0을 반환해야할까? 1을 반환해야할까? 어떤 의미가 담겨있을까 고민을 했던 적이 있다.
- 1을 반환:
1을 반환하는 경우는 일반적으로 “성공” 또는 “올바른 결과”를 의미한다.- 예를 들어, “모든 학생이 짝이 지어졌다는” 성공적인 조건이 만족되었을 때
1을 반환하는 것은 논리적으로 자연스럽다. - 이 값은 함수가 정상적으로 종료되었음을 나타낸다.
- 예를 들어, “모든 학생이 짝이 지어졌다는” 성공적인 조건이 만족되었을 때
- 0을 반환:
0을 반환하는 경우는 보통 “실패” 또는 “조건이 만족되지 않음”을 의미한다.- 만약 기저 사례에서
0을 반환하면 “성공적인 종료”를 의미하기 어려울 수 있다. - 따라서
0을 반환하면, 이 부분이 “짝을 모두 지을 수 없었다”는 의미로 해석될 수 있다.-1을 사용하는 이유: 보통-1은 “유효하지 않은 인덱스”를 나타내거나, 배열이나 리스트에서 찾을 수 없는 값을 표현할 때 사용된다. 즉,firstFree == -1이 의미하는 바는 “더 이상 짝을 지을 학생이 없다”는 것이다. 일반적으로, 배열의 인덱스나 리스트에서-1은 “유효한 값이 없다”는 뜻으로 자주 사용되기 때문에 이를 이용한 표현은 매우 직관적이다.
- 만약 기저 사례에서
짝지어주기 반복문
firstFree는 아직 짝을 짓지 않은 첫 번째 학생을 가리킨다. pairWith는 firstFree 이후의 학생들 중에서 짝을 지을 수 있는 학생을 차례대로 탐색한다. 반복문을 통해 pairWith가 firstFree와 짝을 지을 수 있는지 확인한다. (즉, pairWith가 짝이 안 지어졌고, firstFree와 친구 관계인지 확인) 짝을 지을 수 있으면, firstFree와 pairWith를 짝지은 후, 재귀적으로 나머지 학생들을 짝을 지어 나간다. 재귀 호출이 끝나면 백트래킹을 통해 firstFree와 pairWith의 짝을 다시 풀고, 다른 가능성도 탐색한다.
Reference
나의 뇌