아마추어 팀블로그

알고리즘 문제ID PICNIC C언어 풀이 본문

IT/IT 개발

알고리즘 문제ID PICNIC C언어 풀이

탓치 2016. 1. 25. 08:17

알고리즘 풀이 두 번째 문제는 교재 알고리즘 문제해결전략 6.4장소풍(Picnic)입니다.

문제 링크: 알고스팟 소풍


문제는 위 링크를 눌러 확인해주세요. 그럼 바로 풀이를 보도록 하겠습니다.



#include <stdio.h> #pragma warning(disable:4996) int C, c; // Num of Cases int n, m, m_idx; // Num of students, num of pairs int f[10][10]; // i, j가 친구 사이면 f[i][j] == f[j][i] == 0 int matched[10]; // 짝이 지어진 사람은 1, 아직이면 0 int func(int cnt, int total, int *way) { int ret = 0, i, j; if (cnt == total) return 1; // All matched // 매칭 시킬 녀석을 선택함: i for (i = 0; i < n; i++) if (matched[i] == 0) break; for (j = i + 1; j < n; j++) { if (matched[j] == 1) continue; // 이미 짝이 있는 사람은 무시 if (f[i][j] == 1 && f[j][i] == 1) // i와 j가 친구인 경우 { // 매칭 되었다고 표시한 뒤, 이 둘을 제외한 나머지에 대해 // func() 함수 호출하여 짝지을 수 있는 경우의 수를 반영한다. matched[i] = matched[j] = 1; if (1 == func(cnt + 2, total, way)) (*way)++; // i의 짝이 다른 사람인 경우도 세어 봐야하므로, 다시 매칭되지 않았다고 표시 후 다음 사람에 대한 for문으로 넘어감 matched[i] = matched[j] = 0; } } return 0; } int main(void) { int i, j; scanf("%d", &C); for (c = 0; c < C; c++) { scanf("%d %d", &n, &m); // Reset Friend Info for (i = 0; i < n; i++) for (j = i + 1; j < n; j++) f[i][j] = f[j][i] = 0; for (m_idx = 0; m_idx < m; m_idx++) { int i, j; scanf("%d %d", &i, &j); f[i][j] = f[j][i] = 1; } // Reset Matching Info for (i = 0; i < 10; i++) matched[i] = 0; int way = 0; func(0, n, &way); printf("%d\n", way); } return 0; }

main() 함수에서 총 테스트 케이스 수 C, 총 인원 수 n, 친구 쌍의 수 m, 그리고 m개의 친구 쌍을 입력 받습니다. 그런다음 함수 func()를 호출하죠. 이 함수가 재귀적으로 호출되면서 모든 친구 쌍을 검색할 함수입니다.


함수 func()는 세 개의 인자를 받습니다. 첫 번째 인자는 지금까지 짝지은 사람들의 인원 수입니다. 즉, main()에서 호출할 때에는 아직 아무 짝도 정해지지 않았으므로 0을 전달합니다. 두 번째 인자는 총 인원 수입니다. 사실 인원 수 변수 n이 전역 변수라 갖다 쓸 수도 있었지만 그냥 넣어봤습니다. 생략해도 전혀 상관없습니다. 마지막 변수는 짝을 지을 수 있는 방법의 수, 즉 이 picnic 문제에서 요구하는 답입니다. 이렇게 함수 func()를 호출할 준비가 되었습니다.


int func(int cnt, int total, int *way)


함수 func()가 하는 일은 단순합니다. 총 total 명의 인원 중 cnt 만큼의 인원이 짝을 지은 상태에서, 나머지 total - cnt 명의 인원에 대해 짝을 지을 수 있는 방법의 수를 찾아 *way에 추가합니다. 만일, func()를 호출했을 때 cnt == total, 즉 모든 짝이 지어진 상태라면 1을 반환하여 종료를 알립니다. 자세한 설명은 주석으로 표기해 뒀으니 참고바랄게요.




Comments