c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q56 가장 빠른 비상연락망

[문제]

선생님 1명에 학생 14명으로 구성된 한 학급의 비상연락망을 구축하고자 한다. 

0) 14명의 학생 모두 1번씩은 연락을 받아야 하며, 선생님은 모든 학생이 연락을 잘 받았는지를 확인해야 한다.

1) 선생님은 각 학생들에게 연락을 직접 취할 수 있다. 

2) 선생님으로부터든 학생으로부터든 연락을 받은 학생은 다른 학생한테 연락을 취할 수 있다.

3) 1)의 경우에는 학생이 직접 선생님으로부터 연락을 받았으므로 다시 선생님한테 회신할 필요가 없다.

4) 2)의 경우에는 연락 받은 학생이 다른 학생에게 연락을 하거나 아니면 선생님에게 회신을 줘야 한다. 

5) 연락 시간은 회당 1분이며, 한 번에 1번만 취할 수 있다. (동시에 2명에게 연락할 수 없다.)

 

[예시1] 총 걸린 시간은 9분이고, 선생님 연락 횟수는 4회 (송신 2번, 수신 2번)

 

[예시2] 총 걸린 시간은 9분이고, 선생님 연락 횟수는 9번 (송신 3번, 수신 6번)

모든 학생이 연락을 잘 받았는지 선생님이 확인하는데까지 걸리는 시간을 최소화하고자 한다. 이 때 걸리는 시간은?

또한, 위 조건에서 선생님이 가능하면 적은 횟수로 송, 수신을 하고자 한다. 최소 횟수는?

(위 예시들을 보면 같은 9분이 소요되더라도 선생님이 연락을 취한 횟수는 서로 다르다.)

 

[알고리즘] 

처음 문제를 봤을 때 난감했는데, 생각보다 엄청 복잡하고 난해한 문제는 아니다.

학생을 2 그룹으로 나눈다. 

A 그룹 : 선생님에게 회신할 의무가 있는 학생들

B 그룹 : 선생님에게 회신할 의무가 없는 학생들

A 그룹 학생들은 선생님이 아닌 다른 학생으로부터 연락을 받은 학생들이다.

B 그룹 학생들은 선생님으로부터 직접 연락을 받았거나, 아니면 다른 학생에게 연락을 취함으로써 그 의무를 다음 학생에게 넘긴 학생들이다.

위 그림에서 학생 1과 학생 2는 선생님으로부터 직접 연락을 받았으므로 회신 의무가 없다. 그러므로 처음부터 B그룹에 속해 있다.

학생 3과 학생 4는 학생 1, 학생 2로부터 연락을 받았으므로 처음에는 A 그룹에 속해 있었으나, 다시 학생 5, 학생 6에게 연락을 취함으로써 B 그룹으로 옮겨간 케이스이다.

학생 5와 학생 6은 A 그룹이다.

이제 비상연락망의 구체적인 조직도는 생각하지 않고, 아래 4개의 변수만 고려한다.

시간, A그룹 학생 수, B그룹 학생 수, 선생님 연락 횟수 => (time, a, b, cnt)라고 하자.

 

위 예시 1처럼 진행된다고 했을 때 각각의 변수는 다음과 같다.

0분) (0, 0, 0, 0)

1분) (1, 0, 1, 1)

2분) (2, 1, 2, 2)

3분) (3, 2, 3, 2)

4분) (4, 2, 5, 2)

5분) (5, 2, 7, 2)

6분) (6, 2, 9, 2)

7분) (7, 2, 11, 2)

8분) (8, 1, 13, 3)

9분) (9, 0, 14, 4) 

종료 조건 : a = 0, b = 14

=> 이때의 총 걸린 시간은 9분, 연락 횟수는 4회

 

위 예시 2처럼 진행된다고 했을 때 각각의 변수는 다음과 같다.

0분) (0, 0, 0, 0) 

1분) (1, 0, 1, 1) : 총 1명 증가. B 1명 증가

2분) (2, 1, 2, 2) : 총 2명 증가. A 1명 증가. B 1명 증가.

3분) (3, 3, 4, 3) : 총 4명 증가. A 4명 증가. 기존 A에서 B로 2명 이동 (2명 타 학생에게 연락). 실질적으로 A는 2명만 증가. 

4분) (4, 4, 7, 4) : 총 4명 증가. A 4명 증가. 기존 A에서 B로 3명 이동 (2명은 타 학생에게 연락, 1명은 선생님께 회신) 

5분) (5, 4, 10, 5) : 총 3명 증가. A 3명 증가. 기존 A에서 B로 3명 이동 (2명은 타 학생에게 연락, 1명은 선생님 회신)

6분) (6, 3, 11, 6) : 총 인원 증가X. A에서 B로 1명 이동 (선생님 회신)

7분) (7, 2, 12, 7) : 총 인원 증가X. A에서 B로 1명 이동 (선생님 회신)

8분) (8, 1, 13, 8)

9분) (9, 0, 14, 9) 

종료 조건 : a = 0, b = 14. 이 때의 걸린 시간과 선생님 연락 횟수는 9분, 9회.

 

사실 위와 같이 진행할 때, 총 인원이 14명에 도달하면, 그 이후는 진행할 필요가 없다.

예를 들어, 5분에 (5, 4, 10, 5)이므로 14명이 모두 연락을 받았다.

이 때 A 그룹에는 4명이 남아 있다. A 그룹 학생들이 1분에 1명씩 선생님에게 회신을 하므로,

결국 최종 걸리는 시간은 5분에 4를 더한 9분, 최종 연락 횟수도 마찬가지로 5회에 4를 더한 9회가 된다.

[예시1] f(8, 1, 13, 3) => 8분에 1을 더해 최종 9분, 3회에 1을 더해 최종 4회

[예시2] f(5, 4, 10, 5) => 5분에 4를 더해 최종 9분, 5회에 4를 더해 최종 9회

 

이 문제의 핵심은 A그룹 학생을 최소한으로 하면서 학생 수를 늘려 나가는 것이다!!

예시 1은 A 그룹 학생 수를 2명으로 유지한채 진행했고, 예시 2는 A 그룹 학생 수가 4명까지 증가했는데, 이 차이가 결국은 최종 시간 및 횟수에 영향을 준 것이다.

 

 

이제 어떤 주어진 상태 (time, a, b, cnt)에서 다음에 올 선택지에 대해서 알아보자.

P 명의 학생에게 연락을 취한다고 할 때, 선택지는 크게 3가지가 가능하다.

1) 1명은 선생님이 직접 연락을 하고, 나머지 P - 1 명에 대해서는 학생들이 연락을 하는 경우

(α + β + 1 = P)

A 그룹에는 가능한 한 최소한의 인원만 있는 것이 좋으므로 β는 최소한의 숫자여야 한다.

P - 1이 a 이하라면 β는 0이어야 한다.

(time, a, b, cnt) => (time + 1, a + β, b + α + 1, cnt + 1) (단, P = α + β + 1)

 

2) 선생님은 가만히 있고, P 명에 대해서 학생들이 연락을 하는 경우

(α + β = P)

마찬가지로 가능한 한 A 그룹 인원 수가 적어야 하므로, α는 최대로, β는 최소로 해야 한다.

P가 a 이하라면 β는 0이다.

(time, a, b, cnt) => (time + 1, a + β, b + α, cnt) (단, P = α + β)

 

3) P 명에 대해서 학생들이 연락을 하며, A 그룹의 1명은 선생님에게 회신을 하는 경우

(α + β = P)

마찬가지로 α는 최대로, β는 최소로 해야 한다.

P가 a - 1 이하라면 β = 0이어야 한다.

(time, a, b, cnt) => (time + 1, a + β - 1, b + α + 1, cnt + 1) (단, P = α + β)

 

 

이제 P의 크기에 따라서 위에서 살펴본 1) ~ 3) 중 어떤 선택이 가능한지 살펴본다.

연락을 받을 수 있는 학생 수 P는 최소 1명 부터 최대 a + b + 1 까지 가능하다. 

ㄱ) P < a 인 경우

ㄱ - 1) (time + 1, a, b + P, cnt + 1) - 무의미한 선택지

ㄱ - 2) (time + 1, a, b + P, cnt)

ㄱ - 3) (time + 1, a - 1, b + P + 1, cnt + 1)

위 중에서 1)은 2) 대비 다른 건 다 동일하고 cnt 만 1 더 많으므로 무의미한 선택지이다.

2)와 3)은 뭐가 더 유리한지 아직 알 수 없다! 따라서 2가지 다 탐색해본다.

 

ㄴ) P == a 인 경우

ㄴ - 1) (time + 1, a, b + P, cnt + 1) - 무의미한 선택지

ㄴ - 2) (time + 1, a, b + P, cnt)

ㄴ - 3) (time + 1, a, b + P, cnt + 1) - 무의미한 선택지

1)과 3)은 2) 대비 cnt만 1 더 많으므로 무의미한 선택지이다.

 

ㄷ) P < a + b + 1  인 경우

ㄷ - 1) (time + 1, P - 1, a + b + 1, cnt + 1)

ㄷ - 2) (time + 1, P, a + b, cnt)

ㄷ - 3) (time + 1, P, a + b, cnt + 1) - 무의미한 선택지

3)은 2) 대비 cnt만 1 더 많으므로 무의미한 선택지이다.

1)과 2)는 뭐가 더 유리한지 아직은 알 수 없다!

 

ㄹ) P == a + b + 1 인 경우

ㄹ - 1) 만 가능하다 : (time + 1, P - 1, a + b + 1, cnt + 1)

 

위 내용을 코드로 작성하면 다음과 같다.

#include <stdio.h>
#include <stdbool.h>
#define N 14

int minTime = N;
int minCnt = N;

void solve(int t, int a, int b, int cnt);
int main() {
    int a = 0;
    int b = 0;
    int time = 0;
    int cnt = 0;

    solve(time, a, b, cnt);
    printf("minTime: %d, minCnt: %d\n", minTime, minCnt);
}
void solve(int t, int a, int b, int cnt) {
    if (t + a > minTime) {
        return;
    }
    if (a + b == N) {
        int time = t + a;
        int count = cnt + a;
        if (time < minTime) {
            minTime = time;
            minCnt = count;
        }
        if (time == minTime) {
            minCnt = minCnt < count ? minCnt : count;
        }
        return;
    }

    for (int plus = 1; plus <= (a + b + 1); plus++) {
        if (a + b + plus > N)
            break;
        if (plus < a) {
            solve(t + 1, a, b + plus, cnt);
            solve(t + 1, a - 1, b + plus + 1, cnt + 1);
        }
        else if (plus == a) {
            solve(t + 1, a, b + plus, cnt);
        }
        else if (plus < a + b + 1) {
            solve(t + 1, plus - 1, a + b + 1, cnt + 1);
            solve(t + 1, plus, a + b, cnt);
        }
        else {
            solve(t + 1, plus - 1, a + b + 1, cnt + 1);
        }
    }
}

정답은 아래와 같다.

 

14명일 때는 순식간에 구할 수 있다.

다만, 학생 수가 커지면 (한 50명 정도) 수십 초 이상 소요된다.

따라서 메모 기능을 활용한다.

어떤 상태, 예를 들어 (3, 4, 3, 2) 같은 상태는 여러 번 반복해서 등장할 수 있다.

따라서 (3, 4, 3, 2)가 한 번 사용된 후에는 이를 메모장에 사용했음으로 기록해두면 이후 탐색에서는 더 이상 진행할 필요가 없다.

(3, 4, 3, 2) 뿐만 아니라 time, cnt가 각각 3분, 2회 이상인 모든 케이스들은 더 이상 탐색할 필요가 없다.

따라서 (4, 4, 3, 2), (5, 4, 3, 2) .... (3, 4, 3, 3), (3, 4, 3, 5) ... (4, 4, 3, 3), .... 역시 사용했음으로 기록해두면 된다.

메모 기능을 반영한 코드는 아래와 같다.

 

#include <stdio.h>
#include <stdbool.h>
#define N 50

int minTime = N;
int minCnt = N;
bool memo[N + 1][N + 1][N + 1][N + 1] = { false };

void solve(int t, int a, int b, int cnt);
int main() {
    int a = 0;
    int b = 0;
    int time = 0;
    int cnt = 0;

    solve(time, a, b, cnt);
    printf("minTime: %d, minCnt: %d\n", minTime, minCnt);
}
void solve(int t, int a, int b, int cnt) {
    if (memo[t][a][b][cnt])
        return;

    if (a + b == N) {
        int time = t + a;
        int count = cnt + a;
        if (time < minTime) {
            minTime = time;
            minCnt = count;
        }
        if (time == minTime) {
            minCnt = minCnt < count ? minCnt : count;
        }
        return;
    }

    for (int plus = 1; plus <= (a + b + 1); plus++) {
        if (a + b + plus > N)
            break;
        if (plus < a) {
            solve(t + 1, a, b + plus, cnt);
            solve(t + 1, a - 1, b + plus + 1, cnt + 1);
        }
        else if (plus == a) {
            solve(t + 1, a, b + plus, cnt);
        }
        else if (plus < a + b + 1) {
            solve(t + 1, plus - 1, a + b + 1, cnt + 1);
            solve(t + 1, plus, a + b, cnt);
        }
        else {
            solve(t + 1, plus - 1, a + b + 1, cnt + 1);
        }
    }

    for (int time = t; time <= N; time++) {
        for (int count = cnt; count <= N; count++) {
            if (memo[time][a][b][count])
                break;
            memo[time][a][b][count] = true;
        }
    }
}

n = 50인 경우에도 순식간에 정답을 구할 수 있다!

n = 50명일 때