컬러 퍼즐 최저 횟수 계산 알고리즘 바이브 코딩

이준영·2025년 11월 6일

목표

내가 생각하기에는 최저 횟수를 정하는 방법에는 3가지 정도 방법이 있다고 생각한다.

개발자가 임의로 정함.
개발자가 설계한 퍼즐을 직접 해결하며 횟수를 계산
계산 알고리즘을 만들기

그래서 나는 3번 계산 알고리즘을 만들어 보기로 하였다.
하지만 나는 매우 알고리즘에 약하기 때문에 AI의 도움을 받아 만들어 보기로 하였다.

알고리즘 설계: BFS와 상태 관리

BFS 선택 이유: 최단 경로(최소 이동 횟수)를 보장하기 위해 BFS를 사용함.

BoardState

CellColor[,] Colors: 보드 상태를 저장하는 배열.
Depth: 현재까지의 이동 횟수.
동일한 보드 상태를 중복 탐색하지 않기 위해 HashSet<BoardState>에 저장해야 함.
IEquatable<BoardState> 구현 및 GetHashCode() 캐싱 전략 (int.MinValue를 사용한 캐싱 및 2차원 배열 순회)을 통해 효율성과 정확성을 동시에 확보함.

핵심 헬퍼 함수 구현

FloodFillState

FloodFillState(): BFS의 상태 전이(State Transition)를 담당하는 함수. 현재 영역을 찾아 새 색상으로 칠하는 로직.

GetAdjacentColors

현재 플러드 영역과 인접한 색상 목록을 찾는 로직. 이 색상들이 다음 이동 후보가 됨.

IsBoardMonochromatic

목표 도달 조건 (보드 전체가 단색인지)을 확인하는 함수.

핵심 코드

BFSSolver

시행 착오

기능 테스트

Test Code

Test Board

문제 발생

문제 발생

원인 분석

TrySolve에 Debug.Log 추가

public bool TrySolve(CellColor[,] initialColors, CellColor targetColor, out int minMoves)
{
    // ... (초기화 로직) ...

    while (queue.Count > 0)
    {
        var current = queue.Dequeue();
        
        // ★★★ 1. 탐색 진행 상황 확인 ★★★
        Debug.Log($"Depth: {current.Depth}, Queue Size: {queue.Count}, Visited Count: {visited.Count}");

        // 2. 목표 도달 확인
        if (SolverHelpers.IsBoardMonochromatic(current.Colors) && current.Colors[0, 0] == targetColor)
        {
            // ... (성공 로직) ...
            return true;
        }
        
        // ★★★ 2. 다음 이동 후보 색상 확인 ★★★
        var nextMoveColors = SolverHelpers.GetAdjacentColors(current.Colors);
        Debug.Log($"  Next Move Candidates: {string.Join(", ", nextMoveColors)}"); 
        
        if (nextMoveColors.Count == 0 && !SolverHelpers.IsBoardMonochromatic(current.Colors))
        {
             // ★★★ 3. 막힌 경로 경고 ★★★
             // 보드가 다 칠해지지 않았는데 다음 이동 색상이 없다면 FloodFillState나 GetAdjacentColors에 문제가 있습니다.
             Debug.LogWarning($"  [ERROR] Cannot proceed at Depth {current.Depth}. Check FloodFill logic.");
        }

        // ... (다음 상태 생성 및 큐에 추가 로직) ...
    }
    
    // ... (실패 로직) ...
    return false;
}

Test

Next Move Candidates 가 빈 Hash Set을 리턴

Gemini의 최종 분석

해결책

해결책
TrySolve 코드에 다음 if문을 추가.


var nextMoveColors = SolverHelpers.GetAdjacentColors(current.Colors); 
Debug.Log($"  Next Move Candidates: {string.Join(", ", nextMoveColors)}");

// ★★★ 최종 단계 오류 해결을 위한 중요 수정 ★★★
// 만약 현재 상태가 보드 전체를 통일할 수 있는 상태라면, 목표 색상을 후보에 추가해야 합니다.
// (보드 전체가 단색으로 통일될 수 있는 마지막 색상은 인접 색상이 없을 수 있기 때문)

// 3-1. 현재 플러드 영역의 색상과 목표 색상이 다르고,
//      Flood Fill을 한 번 더 수행하면 보드 전체가 칠해질 가능성이 있다면
if (current.Colors[0, 0] != targetColor)
{
    // 보드 전체 셀 개수
    const int TotalCells = SolverHelpers.Rows * SolverHelpers.Cols;
    
    // 목표 색상으로 칠했을 때 플러드 영역이 보드 전체를 덮을 수 있는지 체크
    var tempColors = (CellColor[,])current.Colors.Clone();
    SolverHelpers.FloodFillState(tempColors, targetColor);
    
    var finalRegion = SolverHelpers.GetFloodRegionCells(tempColors);
    
    if (finalRegion.Count == TotalCells)
    {
        // 목표 색상으로 마지막 이동이 가능하다면 후보에 추가 (중복 방지)
        nextMoveColors.Add(targetColor);
        // Debug.Log($"  [FIX] Added TargetColor ({targetColor}) as final move candidate.");
    }
}
// ★★★ 여기까지 최종 수정 ★★★