c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q41 카드를 뒤섞어 역순 만들기 (2가지 방법 - 깊이우선탐색, 너비우선탐색)

[문제] 1 ~ 10까지 적힌 카드가 각각 1장씩 총 10장이 있고, 1, 2, 3, 4, ... , 10 순으로 일렬로 배치되어 있다.

이 카드를 다음과 같이 섞고자 한다.

연속된 카드 5장을 꺼내서 맨 앞에 배치. (아래 그림 참조)

 

이런 식으로 반복하여 섞는다고 할 때, 카드 배치가 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 (원래 카드의 역순)이 되도록 하고자 한다.

최소 횟수로 섞는다고 할 때, 그때의 횟수는?

 

 

[알고리즘 #1] 깊이 우선 탐색

10장의 카드에서 5장을 꺼낼 수 있으므로, 꺼내는 카드 뭉치에서 제일 앞에 위치한 카드의 위치는 [1] 부터 [5]까지 가능하다.

[1]부터 꺼내는 것을 C1, [2]부터 꺼내는 것을 C2, ... [5]부터 꺼내는 것을 C5라고 한다.

우선, 내가 그동안 주로 사용해왔던 깊이 우선 탐색 방법을 사용하면 다음과 같이 해야 한다.

C1 -> C1 -> C1 -> .... 부터

C5 -> C5 -> C5 -> .... 까지

모든 케이스에 대해서 타겟(역순배열)이 나타나는지 확인한다. 하지만, 이 방법은 2가지 문제가 있는데,

1) 우선, 당연히 C1 -> C1 -> ... 이렇게 계속 진행해 나가면 절대로 타겟이 나타나지 않는다.

(실제로 C1을 연속으로 6번 하면 원래의 자신으로 회귀한다.)

따라서 무한히 진행해야 하고, 프로그램은 끝나지 않는다. 

따라서 적당한 값으로 리밋을 걸어줘야 하는데

(예를 들어 섞는 횟수는 최대 15회까지만 진행한다고 할 때,

C1 -> C1 -> ... C1 -> C1 과 같이 C1을 총 15회 했음에도 정답이 나타나지 않으면 다음 단계인 

C1 -> C1 -> ... C1 -> C2로 넘어간다.)

정답이 몇 회인지 전혀 감을 잡을 수 없는 상태에서 리밋을 얼마로 해야하는지 결정을 하기가 어렵다.

 

2) 무작정 적당히 큰 값을 리밋으로 건다고 해도 문제인 것이

예를 들어 100회 이전에는 무조건 정답이 나타날 것이므로 100을 리밋으로 걸면, 탐색 수가 너무너무 많아지게 된다.

물론 탐색을 하는 과정에서 50번만에 타겟을 찾았다고 하면, 다음 탐색부터는 리밋을 50으로 줄이고,

20번만에 타겟을 찾았다고 하면, 그 다음 탐색부터는 리밋을 20으로 줄이는 방식으로

탐색 수를 줄일 수는 있겠으나, 그럼에도 불구하고 탐색 수가 여전히 많은 것은 사실이다.

 

일단, 깊이 탐색을 이용한 코드는 아래와 같다.

리밋은 처음에는 15회로 걸었다.

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define TOTAL 10
#define MAX_CNT 15					// 깊이 탐색 리밋
void solve(int* card, int* pos, int cnt);
void shuffle(int* card, int* shuffled, int pos);
bool checkCard(int* card, int* target, int sz);
void copy_arr(int* arr1, int* arr2, int sz);
void print_arr(int* arr, int sz);
int start[TOTAL] = { 0 };
int target[TOTAL] = { 0 };
int memo[MAX_CNT][TOTAL] = { 0 };
const int n = 5;					// 섞을 카드 개수
int min_cnt = MAX_CNT;
int main() {
    int pos[MAX_CNT] = { 0 };
    int cnt = 0;
    for (int i = 0; i < TOTAL; i++)
        start[i] = i + 1;
    for (int i = 0; i < TOTAL; i++)
        target[i] = TOTAL - i;
    solve(start, pos, cnt);
    printf("min_cnt = %d\n", min_cnt);
}
void solve(int* card, int* pos, int cnt) {
    if (checkCard(card, target, TOTAL) == true) {
        min_cnt = min_cnt < cnt ? min_cnt : cnt;
        if (cnt == min_cnt) {
            printf("cnt = %d: ", cnt);
            print_arr(pos, MAX_CNT);
        }
        return;
    }
    if (cnt >= min_cnt) {		
        //print_arr(pos, MAX_CNT);
        return;
    }
    for (int p = 1; p <= TOTAL - n; p++) {
        if (cnt > 0 && p == 5)
            if (pos[cnt - 1] == 5)	
                continue;

        pos[cnt] = p;
        shuffle(card, memo[cnt], p);
        solve(memo[cnt], pos, cnt + 1);
        pos[cnt] = 0;
    }
}
void shuffle(int* card, int* shuffled, int pos) {
    for (int i = 0; i < TOTAL; i++) {
        if (i < pos)
            shuffled[i + n] = card[i];
        else if (i < n + pos)
            shuffled[i - pos] = card[i];
        else
            shuffled[i] = card[i];
    }
}
bool checkCard(int* card, int* target, int sz) {
    for (int i = 0; i < sz; i++) {
        if (card[i] != target[i])
            return false;
    }
    return true;
}
void copy_arr(int* arr1, int* arr2, int sz) {
    for (int i = 0; i < sz; i++)
        arr1[i] = arr2[i];
}
void print_arr(int* arr, int sz) {
    for (int i = 0; i < sz; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

아래는 결과.

정답이 12회인 것은 나왔으나, 예상처럼 시간은 오래 걸린다.

그나마 다행인 것이 맨 앞이 C1로 시작하는 가짓수가 있어서 그나마 시간이 단축될 수 있었다.

또한, C5가 2번 연속으로 오면 원래의 자신으로 회귀하므로, C5가 연속 2번 등장하는 경우는 제외하여, 탐색 수를 조금이라도 줄일 수 있다.

하지만, 이런 방법은 한계가 있다.

따라서, 이번 문제는 너비 우선 탐색으로 푸는 것이 더 좋은 방법이다.

 

[알고리즘 #2]

깊이우선탐색과 너비우선탐색 비교(출처 : 나무위키)

 

너비 우선 탐색은 다음과 같이 탐색하는 것이다.

C1, C2, C3, C4, C5를 검사한다. 타겟이 없으면 다음 단계로 넘어가서

C1C1 (C1을 2번 진행한 것), C1C2, C1C3, C1C4, C1C5, ... C5C5를 검사한다.

만약 여기서도 정답이 없으면

C1C1C1, C1C1C2, ... C5C5C5를 검사한다.

이런식으로 반복하여

타겟이 나타날 때까지 진행하는 것이다.

너비우선 탐색을 위해서 아래와 같이 진행한다.

섞는 횟수를 1회 진행하면 { C1, C2, C3, C4, C5 } 배열이 생긴다. (C1, C2,... 각각은 카드 배열이므로 2차원 배열이다)

이 배열을 메모장에 기록해두고, 다음 단계를 진행한다. (섞는 횟수 2회인 경우 탐색)

이번에는 25가지 경우가 생기는데 { C1C1, C1C2, C1C3, ... C5C5 }

이를 마찬가지로 메모장에 기록해둔다.

단, 문제는 1번 진행할 때마다 배열의 크기가 5배씩 커지고, 정답인 12회까지 진행하게 되면 배열의 크기는 5의 12승인 

244,140,625가 된다.

이에, 책에서는 다음과 같은 방법을 제시했다.

순방향으로만 진행하지 말고, 역방향도 함께 진행하는 것이다.

{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }에서부터 탐색을 시작해나가면서 memoFW에 카드 배열을 저장한다.

{ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }에서도 거꾸로 탐색을 해 나가면서 memoBW에 카드 배열을 저장한다.

그리고 memoFW와 memoBW에 공통 원소로 들어가 있는 카드 배열이 있는지 확인하면 된다.

이를 코드로 나타내면 다음과 같다.

 

#include <stdio.h>
#include <math.h>
#include <stdbool.h>
#define N 10
#define SH 5
#define SZ 390625 // pow(5, 8)
int memoFW[SZ][N] = { 0 };
int memoBW[SZ][N] = { 0 };
int temp[SZ][N] = { 0 };
void shuffleFW(int* card, int* shuffled, int pos);
void shuffleBW(int* card, int* shuffled, int pos);
bool checkCard(int* card, int* target, int sz);
void copy_arr(int memo[][N], int temp[][N]);
int main() {
    for (int i = 0; i < N; i++) {
        memoFW[0][i] = i + 1;	// { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }
        memoBW[0][i] = N - i;	// { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }
    }
    int cnt = 0;
    int state = false;
    while (state == false) {
        for (int i = 0; memoFW[i][0] != 0; i++) {
            for (int j = 1; j <= N - SH; j++) {
                int k = (N - SH) * i + j - 1;
                shuffleFW(memoFW[i], temp[k], j);
                for (int l = 0; memoBW[l][0] != 0; l++) {
                    if (checkCard(temp[k], memoBW[l], N) == true) {
                        state = true;
                        break;
                    }
                }
                if (state == true)	break;
            }
            if (state == true)	break;
        }
        copy_arr(memoFW, temp);
        cnt++;

        for (int i = 0; memoBW[i][0] != 0; i++) {
            for (int j = 1; j <= N - SH; j++) {
                int k = (N - SH) * i + j - 1;
                shuffleBW(memoBW[i], temp[k], j);
                for (int l = 0; memoFW[l][0] != 0; l++) {
                    if (checkCard(temp[k], memoFW[l], N) == true) {
                        state = true;
                        break;
                    }
                }
                if (state == true)	break;
            }
            if (state == true) break;
        }
        copy_arr(memoBW, temp);
        cnt++;
    }
    printf("cnt = %d\n", cnt);
}
void shuffleFW(int* card, int* shuffled, int pos) {
    for (int i = 0; i < N; i++) {
        if (i < pos)
            shuffled[i + SH] = card[i];
        else if (i < SH + pos)
            shuffled[i - pos] = card[i];
        else
            shuffled[i] = card[i];
    }
}
void shuffleBW(int* card, int* shuffled, int pos) {
    for (int i = 0; i < N; i++) {
        if (i < SH)
            shuffled[i + pos] = card[i];
        else if (i < SH + pos)
            shuffled[i - SH] = card[i];
        else
            shuffled[i] = card[i];
    }
}
bool checkCard(int* card, int* target, int sz) {
    for (int i = 0; i < sz; i++) {
        if (card[i] != target[i])
            return false;
    }
    return true;
}
void copy_arr(int memo[][N], int temp[][N]) {
    for (int i = 0; temp[i][0] != 0; i++) {
        for (int j = 0; j < N; j++) {
            memo[i][j] = temp[i][j];
        }
    }
}

정답은 동일하게 나오고, 시간은 1초 미만으로 걸렸다.

 

시간적으로 봤을 때은 너비 우선 탐색이 더 좋은 방법이다.

다만, 깊이 우선 탐색도 장점은 있는데, 구체적인 섞는 방법을 알 수 있고, 같은 12회라도 총 몇 가지 케이스가 가능한지 확인할 수 있다는 점이다.