한붓 그리기 경우의 수 계산

 

게임 속에 미니게임을 하나 넣기 위해

이런 툴을 대충 만들어다 작업자에게 던졌고

그 아웃풋이 이렇게 저렇게 전달되어 다시 나에게 온 걸 보니 상태가 영 좋지 않았다.

 

그렇다고 내가 직접 500개 되는 스테이지 후보에서 골라보자니

좀 귀찮았다.

 

한붓 그리기를

오일러 트레일(보통 한붓 그리기)

오일러 서킷(출발점으로 돌아오는 버전)

라고 한다는데 대충 구글링을 해본 결과 대강 손수 만들어서 쓰고 버리는 게 더 빠를 것 같아서 만들어보았다.

 

 

 

 

public class OneLineDrawLevelClass {
    public string levelId;
    public int levelIndex;
    public List<Vector2> points = new List<Vector2>();
    public List<int> connectionFromList = new List<int>();
    public List<int> connectionToList = new List<int>();

}

 

 

 

 

for (int i = 0; i < levelClasses.Length; i++) {
            List<int> fromList = new List<int>();
            List<int> toList = new List<int>();
            for (int c = 0; c < levelClasses[i].connectionFromList.Count; c++) {
                fromList.Add(levelClasses[i].connectionFromList[c]);
                toList.Add(levelClasses[i].connectionToList[c]);
                fromList.Add(levelClasses[i].connectionToList[c]);
                toList.Add(levelClasses[i].connectionFromList[c]);
            }

            int failCount = 0;
            int sucessCount = 0;
            for (int p = 0; p < levelClasses[i].points.Count; p++) {
                (int, int) temp = TryPath(p, fromList, toList);
                sucessCount += temp.Item1;
                failCount += temp.Item2;
            }

            //Debug.Log(levelClasses[i].levelId + " 레벨. 성공: " + sucessCount + " 실패:" + failCount);
        }

 

 

 

 

 

 

    private (int, int) TryPath(int startPos, List<int> remainFrom, List<int> remainTo) {

        int successCount = 0;
        int failCount = 0;

        List<int> startPossibility = new List<int>();
        for (int i = 0; i < remainFrom.Count; i++)
            if (remainFrom[i] == startPos) startPossibility.Add(i);

        
        for (int i = 0; i < startPossibility.Count; i++) {
            int foundIndex = startPossibility[i];
            int destPos = remainTo[foundIndex];
            

            if ((foundIndex % 2) == 1) foundIndex--;

            List<int> copyRemainFrom = new List<int>(remainFrom);
            List<int> copyRemainTo = new List<int>(remainTo);
            copyRemainFrom.RemoveAt(foundIndex);
            copyRemainTo.RemoveAt(foundIndex);
            copyRemainFrom.RemoveAt(foundIndex);
            copyRemainTo.RemoveAt(foundIndex);

            
            if (copyRemainFrom.Count == 0) { //선 다 썼으면 성공이지.
                
                successCount++;
            } else { //선 남았으면 계속 ㄱㄱ
                (int, int) temp = TryPath(destPos, copyRemainFrom, copyRemainTo);
                successCount += temp.Item1;
                failCount += temp.Item2;
            }
        }

        if (startPossibility.Count == 0) failCount++;

        return (successCount, failCount);
        
    }

 

 

 

 

그래서 컴퓨터한테 시켰다.

아무 점에서 아무 선부터 시작했을 때 경우의 수, 성공 수, 실패 수, 성공률을 구해서 CSV로 뽑았다.

그랬더니 몬가... 몬가 규칙성도 보이고 한다.

 

 

그런데 난이도 좀 높은 문제를 시켰더니 하루종일 연산만 하다가 뻗었다.

유니티로 만들어서 속도가 느려서 더 끔찍하다.

개떡같이 만들긴 했지만 이렇게까지 느릴 줄이야.

 

 

되는 만큼만 구하고 나머지는 직접 선출해야징.