[자료구조] Queue - Josephus problem (feat. C 언어)

문제

 

Josephus problem (요세푸스 문제)?

n과 k가 자연수이고, k < n이라고 가정한다. n명이 동그랗게 모여있을 때 임의의 한 명부터 순서를 세어 k번째 사람을 모임에서 제외한다. 남은 n-1명에서 다시 다음 사람부터 순서를 세서 k번째 사람을 모임에서 제외한다. 이것을 아무도 남지 않을 때까지 계속해서 반복한다. 이때 모임에서 제외되는 사람의 순서를 (n, k) 요세푸스 순열이라고 하며 마지막으로 제외되는 사람을 구하는 문제를 요세푸스 문제라고 한다.
예를 들어 (7,3) 요세푸스 순열은 {3,6,2,7,5,1,4}이며 4번째 위치한 사람이 마지막으로 제외되게 된다.

출처 : 위키백과

 

풀이

 

예를 들어 총 8명의 사람이 동그랗게 모여있다고 하자. 1번 사람의 위치에서 부터 시계방향으로 3번째 순서에 해당하는 사람이 모임에서 제외된다고 하자.

 

Josephus problem 예시

 

1 step은 초기 상태에서 1번 사람의 위치에서 3번째 순서에 해당하는 3번 사람이 모임에서 제외된 단계이다. 2 step은 제외된 3번 사람의 위치에서 3번째 순서에 해당하는 6번 사람이 모임에서 제외된 단계이며 이런 메커니즘으로 마지막에는 한 사람만이 남게 된다. 

 

이러한 메커니즘을 가지고 자료구조 큐를 활용해 풀어보자.

 

Josephus problem을 자료구조 큐로 표현

 

큐에 총 8명의 사람을 front에서부터 오름차순으로 rear까지 나열한다.

 

 

 

1 step은 초기 상태에서 1번, 2번 사람을 순서대로 dequeue 연산 후 큐에 enqueue 연산을 진행한다. 그리고 3번째 위치한 사람인 3번 사람은 dequeue 연산만 진행하여 큐에서 제외한다.

 

 

 

2 step과 3 step도 마찬가지로 1 step에서 실행한 일련의 작업들을 진행한다. 이후 같은 작업들을 반복하다보면 마지막에는 큐에 7번 사람만이 남게된다.

 

구현

 

int josephus(struct Queue* queue, int k, int n) // 요세푸스 알고리즘 , 1~k까지 중 n번째 숫자마다 사라지며 마지막 남는 숫자 출력
{
    int index = 1;
 
    for (int i = 1; i <= k; i++) // 큐에 1~k까지 데이터 추가
    {
        enqueue(queue, i);
    }
 
    while (queue->count != 1) // 큐에 데이터가 1개가 남을 때 까지 반복한다
    {
        if (index % n == 0) // n번째에 해당하는 사람을 큐에서 제외한다
        {
            printf("제외 : %d\n",dequeue(queue));
        }
 
        else // n번째에 해당하지 않는 사람은 큐에서 dequeue 후에 바로 enqueue 해준다.
        {
            enqueue(queue, dequeue(queue));
        }
 
        index++;
    }
 
    return printf("마지막으로 남은 사람 = %d\n",dequeue(queue));
}