본문 바로가기

알고리즘/알고리즘 문제해결전략

문제 ID : PICNIC, 난이도: 하

반응형

 

picnic 소풍

 

항상 친구인 학생들 끼리만 짝을 지어주는 프로그램

/*

    테스트 케이스 : C

    학생 수  : N

    학생 짝의 수 : M

    서로 친구인 학생 쌍이 주어진다.

*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
 
int dfs(int taken[11]);
int dfs2(int taken[11]);
 
int taken[11= {0,};
int checkFriend[11][11= {0,};
int C,N,M = 0;
int main(){
    cin >> C;
    for(int i = 0; i < C; i ++){//test case 3번
        cin >> N >> M;
        for(int j = 0; j < M; j ++){
            int friend1, friend2;
            cin >> friend1 >> friend2;
        // (1, 2) 와 (2, 1)은 같은 의미이다.(둘이 친구라는 뜻이기 때문에) 
            checkFriend[friend1][friend2] = 1;
            checkFriend[friend2][friend1] = 1;
        }
    }
    int ret = dfs2(taken);
    cout << "ret : "<< ret;
}
 
 
cs

메인함수에서는 위와 같이 입력을 받아서 dfs를 실행하기 위한 조건을 세팅한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int dfs(int taken[11]){
    bool finished = true;
    for(int i = 0; i < N; i ++){
    if(!taken[i]) finished = false;
    }    
    if(finished) return 1;
    
    int ret = 0;
    for(int i = 0; i < N; i ++){
        for(int j = 0; j < N; j ++){
            if(!taken[i] && !taken[j] && checkFriend[i][j]){
                taken[i] = taken[j] = true;
                ret += dfs(taken);
                taken[i] = taken[j] = false;
            }  
        }
    }
    return ret;
}
cs

위의 코드를 보면 완전탐색과 재귀함수를 이용하여 전체를 조회하여 짝을 맞추는 작업을 한다.

ex)

위 코드는 taken으로 학생들이 짝이 지어졌는지 아닌지를 체크하여 전체 함수를 진행한다.

 

만약 taken의 값이 학생수 만큼 모두 {1, 1, 1, 1}이 되면 0번, 1번, 2번, 3번 학생이 모두 짝이 지어진 것으로 보고 1을 return 하여 재귀함수를 끝낸다.

 

 checkFriend[i][j] 값은 main함수에 입력받은 친구 목록이다.

 

하지만 위의 함수에서는 고려하지 않은점이 있다.

바로 중복된 값이다. 

 

(i, j)  (i, j)

(0, 1)  (0, 1)

(2, 3)  (3, 2)

 

(i, j)  (i, j)

(1, 0)  (1, 0)

(2, 3)  (3, 2)

 

위의 값들을 모두 서로 다른 방법으로 생각하여 계산한다.

하지만 실제상황에서는 모두 같은 하나의 짝을 짓는 방법이다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int dfs2(int taken[11]){
    int firstFree = -1;
 
    for(int i = 0; i < N; i ++){
        if(!taken[i]) firstFree = i;
        break;
    }    
    if(fristFree == -1return 1;
 
    int ret = 0;
    for(int pairWith = firstFree + 1; pairWith < N; pairWith ++){
        if(!taken[pairWith] && checkFriend[firstFree][pairWith]){
           taken[firstFree] = taken[pairWith] = true;
            ret += dfs2(taken);
           taken[firstFree] = taken[pairWith] = false;
        }
    }
    return ret;
}
cs

dfs2함수는 위의 중복을 제거하여 올바른 값이 나올 수 있도록 한 것이다.

 

taken[] = {0, 0, 0, 0}

firstFree = 0;

break;

 

checkFriend[0][1] taken[] = {1, 1, 0, 0}

checkFriend[0][2] taken[] = {1, 0, 1, 0}

checkFriend[0][3] taken[] = {1, 0, 0, 1}

 

와 같이 만들어 주면 중복을 배제하고 원하는 값을 얻을 수 있다.

 

반응형