c언어로 알고리즘퍼즐68 (프리렉) 풀기 Q57 수건 돌리기의 총 달린 거리

[문제] n 명의 사람들이 원형으로 앉아 수건돌리기 놀이를 한다. (술래까지 포함하면 총 n + 1 명이다)

편의상 (맨 처음) 술래는 0번이라고 하고, 나머지 사람들은 1 ~ n번이라고 한다.

게임 시작: [1, 2, 3, 4, 5, 6, ..., n - 1, n] // 술래 = 0

1) 게임을 시작할 때 0번은 1번 뒤에 수건을 놓는다. 그리고 시계방향으로 1바퀴를 돈다. 1바퀴 둘레의 길이를 n이라고 하면 0번이 뛴 거리는 n이다.

[0, 2, 3, 4, 5, 6, ..., n - 1, n] // 술래 = 1

2) 이제 1번이 술래가 된다. 1번은 2 ~ n 중에서 놓고 싶은 위치에 수건을 놓을 수 있다. 만약에 5번 뒤에 수건을 놓았다면

[0, 2, 3, 4, 1, 6, ..., n - 1, n] // 술래 = 5

그리고 1번이 뛴 거리는 4 + n이 된다. (5번 위치까지 가서 수건을 놓고 1바퀴를 더 돌아야 하기 때문)

이런 식으로 반복해나간다.

 

이렇게 해서 앉아있는 사람들의 배치를 원래 배치의 역순으로 만들고자 할 때, 술래들이 뛴 거리를 최소로 하고자 한다.

n = 8일 때, 역순으로 만들기 위해 술래가 뛰는 최소 거리는?

아래와 같은 배치면 원래의 역순이 된다.

[1, 8, 7, 6, 5, 4, 3, 2] // [3, 2, 1, 8, 7, 6, 5, 4] // [6, 5, 4, 3, 2, 1, 8, 7] // [7, 6, 5, 4, 3, 2, 1, 8] 등등   

 

 

[알고리즘]

알고리즘은 특별한 것은 없고, 전체 경우에 대해서 탐색을 하면 된다.

[1, 2, 3, 4, 5, 6, 7, 8]에서 시작해서 [1, 8, 7, 6, 5, 4, 3, 2], [2, 1, 8, 7, 6, 5, 4, 3],...,[8, 7, 6, 5, 4, 3, 2, 1] 중 하나에 도달하면 탐색을 멈추고, 그 때까지 뛴 거리를 조사하면 된다.

[i] 위치에서 출발하여 [j]에 도달한 경우 술래가 뛴 거리는 다음과 같다. (기본으로 1바퀴는 뛰어야 하므로 최소 8은 돌아야 한다)

1) j >= i 이면 8 + (j - i)

2) j < i 이면 8 + (8 + j -i)

 

그리고 조금이라도 탐색 수를 줄이기 위해서 다음과 같은 제약 조건을 걸어준다.

제약조건: 술래가 [i]위치에서 출발한 경우 다시 [i]로 되돌아오는 것은 제외한다.

 

이를 코드로 구현하면 다음과 같다.

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

int minLength = 100;
int cnt = 0;
int memo[N * N] = { 0 };

void solve(int* arr, int p, int l, int it, int depth);
void printArr(int* arr, int sz);
int main() {
    int arr[N] = { 0 };
    int pos = 0;		// 술래가 직전 앉았던 위치
    int length = 0;		// 술래가 뛴 거리
    int it = 0;			// 술래 번호
    int depth = 0;		

    // 배열 초기화
    for (int i = 0; i < N; i++)
        arr[i] = i + 1;

    solve(arr, pos, length, it, depth);
    printf("minLength = %d\n", minLength);
    printf("cnt = %d\n", cnt);
}
void solve(int* arr, int p, int l, int it, int depth) {

    if (l > minLength)
        return;

    bool flag;
    // arr[i] == 1이면 다음에 8이 오고, 그 외의 경우엔 arr[i] - 1 이 와야 한다.
    for (int i = 0; i < N - 1; i++) {
        flag = (arr[i + 1] == (arr[i] == 1 ? N : arr[i] - 1));
        if (!flag)
            break;
    }
    if (flag) {
        if (l < minLength) {
            minLength = l;
            cnt = 0;
        }
        if (l == minLength) {
            printf("length = %3d : ", l);
            printArr(memo, depth);
            cnt++;
        }
        return;
    }

    for (int i = 0; i < N; i++) {
        int length = l;
        int newIt = arr[i];		// 새로운 술래
        int newPos = i;			// 새로운 술래의 시작 위치

        if (l == 0 && i != 0)		// 게임 시작할 때 수건 위치는 0으로 고정
            continue;
        if (l != 0 && i == p)		// 방금 앉았던 위치에 다시 놓지 않는다
            continue;
		
        if (p <= i) {
            length += (N + i - p);
        }
        else {
            length += (2 * N + i - p);
        }
        arr[i] = it;				// [i]에 기존 술래가 앉는다.
        memo[depth] = i;
        solve(arr, newPos, length, newIt, depth + 1);
        arr[i] = newIt;				// 탐색이 끝나면 다시 원복
        memo[depth] = 0;
    }
}
void printArr(int* arr, int sz) {
    for (int i = 0; i < sz; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

 

n = 8일 때는 금방 정답을 구할 수 있다.

최소 거리는 96이며, 총 36가지 경우가 가능하다.

 

젤 첫 케이스에 대해서 살펴보면

[1, 2, 3, 4, 5, 6, 7, 8] // 술래 0 // 처음위치 0 // 도착위치 0

=> [0, 2, 3, 4, 5, 6, 7, 8] // 술래 1 // 처음위치 0 // 도착위치 1

=> [0, 1, 3, 4, 5, 6, 7, 8] // 술래 2 // 처음위치 1 // 도착위치 2

=> [0, 1, 2, 4, 5, 6, 7, 8] // 술래 3 // 처음위치 2 // 도착위치 4

=> [0, 1, 2, 4, 3, 6, 7, 8] // 술래 5 // 처음위치 4 // 도착위치 2

=> [0, 1, 5, 4, 3, 6, 7, 8] // 술래 2 // 처음위치 2 // 도착위치 5

=> [0, 1, 5, 4, 3, 2, 7, 8] // 술래 6 // 처음위치 5 // 도착위치 1

=> [0, 6, 5, 4, 3, 2, 7, 8] // 술래 1 // 처음위치 1 // 도착위치 6

=> [0, 6, 5, 4, 3, 2, 1, 8] // 술래 7 // 처음위치 6 // 도착위치 0

=> [7, 6, 5, 4, 3, 2, 1, 8]

 

직관적으로 생각했을 때는 특정 2개 자리는 고정시키고 (예를 들어 2번과 6번은 고정) 나머지 6명이 서로 대칭으로 이동하는 것이 가장 적게 뛰는 경우라고 생각이 드는데 실제로는 그렇지 않다는 것을 알 수 있다.