사천성 마무리 하기 (내일배움캠프 스터디)

사천성 마무리하기

내일부터 본 캠프가 시작된다.

시작되기 전에, 만들고 있던 사천성 게임을 마무리하려고 한다.

 

1. BFS 적용

DFS를 활용해 코드를 짰지만,  사천성은 BFS를 활용하는 것이 더 효율적이라는 생각이 들어 BFS를 적용해봤다.

그리고 매개변수가 너무 많아 복잡해보이던 재귀함수를 정리할 겸 CardInfoForRecursive라는 class를 만들었다.

 

원래 코드

...
	bool IsCardConnected()
    {
        isConneted = false;
        int turnCount = 0;

        Vector3 dir = secondCard.transform.position - firstCard.transform.position;
        
        int[] dx = { 0, 0, 1, -1 };
        int[] dy = { 1, -1, 0, 0 };

        if(dir.x < 0)
            (dx[2], dx[3]) = (dx[3], dx[2]);
        if(dir.y < 0)
            (dy[0], dy[1]) = (dy[1], dy[0]);
        if(Mathf.Abs(dir.x) > Mathf.Abs(dir.y))
            (dx, dy) = (dy, dx);

        cardInfo.dx = dx;
        cardInfo.dy = dy;

        int firstCardNum = firstCard.GetComponent<Card>().cardNum;
        bool[] visited = new bool[cardList.Count];
        visited[firstCardNum] = true;
        int dirNum = 0;

        return CheckCardConnectionRecursive(turnCount, visited, firstCardNum, dirNum, dx, dy);
    }

    bool CheckCardConnectionRecursive(int turnCount, bool[] visited, int tempNum, int dirNum, int[] dx, int[] dy)
    {
        if (isConneted)
            return true;

        int temp = dirNum + 4;
        for (int i = dirNum; i < temp; ++i)
        {
            int index = i % dx.Length;

            int nx = tempNum % xCount + dx[index];
            int ny = tempNum / yCount + dy[index];
            if (nx < 0 || nx >= xCount || ny < 0 || ny >= yCount)
                continue;

            // 카드의 num
            int num = tempNum + dx[index] + (dy[index] * xCount);
            if (num >= cardList.Count || num < 0)
                continue;

            // 방향이 지금까지와 다르다면 ++turnCount
            int tempdir = dirNum;
            int tempTurnCount = turnCount;
            if (tempdir != index)
            {
                if (tempTurnCount < 3)
                    ++tempTurnCount;
                else
                {
                    Debug.Log("회전 횟수 초과 " + num + " dir: " + tempdir);
                    continue;
                }
                tempdir = index;
            }

            // secondCard와 같은 자리라면 true
            if (num == secondCard.GetComponent<Card>().cardNum)
            {
                isConneted = true;
                return true;
            }

            // 카드가 있는 자리라면
            if (cardList[num].activeSelf)
            {
                Debug.Log("자리에 카드 " + num + " dir: " + dirNum);
                continue;
            }

            // 방문한 자리라면
            if (visited[num])
            {
                Debug.Log("방문한 자리 " + num + " dir: " + dirNum);
                continue;
            }
            bool[] tempVisited = (bool[])visited.Clone();
            tempVisited[num] = true;

            if (CheckCardConnectionRecursive(tempTurnCount, tempVisited, num, tempdir, dx, dy))
                return true;
        }

        return false;
    }
    ...

 

 

변경한 코드

class CardInfoForRecursive
{
    public int turnCount;
    public bool[] visited;
    public int num;
    public int dirNum;
    public int[] dx;
    public int[] dy;

    public CardInfoForRecursive(int turnCount, bool[] visited, int num, int dirNum, int[] dx, int[] dy)
    {
        this.turnCount = turnCount;
        this.visited = visited;
        this.num = num;
        this.dirNum = dirNum;
        this.dx = dx;
        this.dy = dy;
    }
}

 

    bool IsCardConnected()
    {
        isConneted = false;

        CardInfoForRecursive cardInfo
            = new(0, new bool[cardList.Count], firstCard.GetComponent<Card>().cardNum, 0, new int[4], new int[4]);

        Vector3 dir = secondCard.transform.position - firstCard.transform.position;
        
        int[] dx = { 0, 0, 1, -1 };
        int[] dy = { 1, -1, 0, 0 };

        if(dir.x < 0)
            (dx[2], dx[3]) = (dx[3], dx[2]);
        if(dir.y < 0)
            (dy[0], dy[1]) = (dy[1], dy[0]);
        if(Mathf.Abs(dir.x) > Mathf.Abs(dir.y))
            (dx, dy) = (dy, dx);

        cardInfo.dx = dx;
        cardInfo.dy = dy;
        
        int firstCardNum = firstCard.GetComponent<Card>().cardNum;
        cardInfo.visited[firstCardNum] = true;

        return CheckCardConnectionRecursive(cardInfo);
    }

    bool CheckCardConnectionRecursive(CardInfoForRecursive cardInfo)
    {
        if (isConneted)
            return true;

        Queue<CardInfoForRecursive> cardQueue = new Queue<CardInfoForRecursive>();

        int temp = cardInfo.dirNum + cardInfo.dx.Length;
        for (int i = cardInfo.dirNum; i < temp; ++i)
        {
            int index = i % cardInfo.dx.Length;

            int nx = cardInfo.num % xCount + cardInfo.dx[index];
            int ny = cardInfo.num / yCount + cardInfo.dy[index];
            if (nx < 0 || nx >= xCount || ny < 0 || ny >= yCount)
                continue;

            // 카드의 num
            int num = cardInfo.num + cardInfo.dx[index] + (cardInfo.dy[index] * xCount);
            if (num >= cardList.Count || num < 0)
                continue;

            // 방향이 지금까지와 다르다면 ++turnCount
            int tempdir = cardInfo.dirNum;
            int tempTurnCount = cardInfo.turnCount;
            if (tempdir != index)
            {
                if (tempTurnCount < 3)
                    ++tempTurnCount;
                else
                {
                    Debug.Log("회전 횟수 초과 " + num + " dir: " + tempdir);
                    continue;
                }
                tempdir = index;
            }

            // secondCard와 같은 자리라면 true
            if (num == secondCard.GetComponent<Card>().cardNum)
            {
                isConneted = true;
                return true;
            }

            // 카드가 있는 자리라면
            if (cardList[num].activeSelf)
            {
                Debug.Log("자리에 카드 " + num + " dir: " + cardInfo.dirNum);
                continue;
            }

            // 방문한 자리라면
            if (cardInfo.visited[num])
            {
                Debug.Log("방문한 자리 " + num + " dir: " + cardInfo.dirNum);
                continue;
            }
            bool[] tempVisited = (bool[])cardInfo.visited.Clone();
            tempVisited[num] = true;

            CardInfoForRecursive card = new(tempTurnCount, tempVisited, num, tempdir, cardInfo.dx, cardInfo.dy);
            cardQueue.Enqueue(card);
        }

        while (cardQueue.Count > 0)
            if(CheckCardConnectionRecursive(cardQueue.Dequeue()))
                return true;

        return false;
    }

바꾼 결과는 굉장히 성공적이다.

재귀함수가 도는 횟수가 현저히 줄었고 카드를 맞출 때 눈에 보이던 버벅거림도 없어졌다.