[Unity/C#] C# 에서 리스트 셔플하기 - C# list shuffle

개요

 최근 덱 빌딩 카드 게임을 개발하다가 일단 덱 빌딩 게임은 각 게임이 시작될 때 카드를 셔플해 두는 게 중요합니다. 그런데 안타깝게도 C#에서 리스트를 바로 셔플 할만한 함수가 없었습니다. C++은 random_shuffle(물론 C++11까지) 같은 함수들이 있어 이를 사용할 수 있는데 C#은 이상하리만큼 이런 쪽 함수들이 적은 느낌이라 직접 구현을 해야 했습니다.

 

 그래서 발견한 알고리즘이 피셔-예이츠 셔플(Fisher-Yates Shuffle)인데 이번 글에서 이를 정리해 보려고 합니다.

 

코드

급한 분들을 위해서 사용한 코드 먼저.

// GameAlgorithm.cs
private static Random rng = new Random();  

public static void Shuffle<T>(this IList<T> list)  
{
    int n = list.Count;  
    while (n > 1) {  
        n--;  
        int k = rng.Next(n + 1);  
        T value = list[k];  
        list[k] = list[n];  
        list[n] = value;  
    }  
}

[ContextMenu("CardShuffle")]
private void ShuffleCard()
{
    Yoot.Algorithm.GameAlgorithm.Shuffle(_playerDeck);
}

 

피셔-예이츠(Fisher-Yate) 셔플 설명

 일단 알고리즘 자체는 정말 간단합니다. 인자로 받은 리스트에서 Random.Next() 함수를 사용해 핸덤한 인덱스 k를 얻은 뒤 이걸 현재의 순서 n과 바꿔주는 역할입니다. 이 경우 편향되지 않은 배열을 생성해주며 시간 복잡도도 O(N)으로 빠른편에 속하게 됩니다. 그래서 이를 활용해서 카드 덱을 랜덤 셔플할 수 있게 되었습니다.

 

 

여기서부터는 C#의 this와 관련한 이야기

 원래라면 따로 이야기를 해야 겠지만 위 코드에서 this가 들어갔기에 이에 대해 궁금하신 분들이 있을까 봐 이렇게 적어봅니다.

public static void Shuffle<T>(this IList<T> list)

위 함수는 함수 파라미터에 'this' 라는 키워드가 함께 있는데 저도 피겨-예이츠 코드를 들고 온 거라 처음에는 이해가 안 됐습니다. 

Use of "this" keyword in formal parameters for static methods in C#

 일단 위와 같은 글을 찾을 수 있는데 해석을 해보면 '외부 함수를 멤버 함수처럼 호출할 수 있게' 해주는 키워드라고 합니다. 그러면 위 Shuffle 함수를

_playerDeck.Shuffle();

이런 식으로 부를 수 있게 하는 것이죠. 그런데 위와 같은 경우 제가 선언을 저렇게 간단하게 하지 않고 함수에 인자를 전달하는 방식 + 네임스페이스 명시를 해서 호출을 했습니다.

 

 이와 같은 일이 있었던 이유는 프로젝트에서 각 클래스별 네임스페이스를 구분해 줬었고 이에 따라 Shuffle() 함수가 들어있는 곳도 네임스페이스를 따로 사용하게 되었던 것입니다. 그래서 사용하기 위해서는

using static Yoot.Algorithm.GameAlgorithm;
//...
_playerDeck.Shuffle();

이런 식으로 사용했어야 하고 이로 인해 함수 콜이 길어지게 된 것입니다.

 

 뭐 this에 대한 정의는 위에 있고...코드가 저렇게 된 데는 이런 이유가 있다는 것이죠. 개인적인 이야기입니다. 이후에 이거에 대해서 생각해 봐야겠네요.

암튼 4개지만 셔플은 잘 됩니다