Exercism - Dominoes 백트래킹, IEnumerable, Tuple

문제요약

연쇄 가능한 패인지 확인하기

 

 

난이도

Hard

---

풀이 포인트

• 백트래킹
  • 문제 해결을 위해 모든 가능한 선택을 시도한 후, 가능성이 없다고 판단되면 이전 단계로 되돌아가거나 이전 결정을 변경
  • 주로 재귀적인 방법
• IEnumerable : 컬렉션 인터페이스, 순차적으로 열거할 수 있게 해주는 기능
• Tuple 

https://machineboy0.tistory.com/230

분할정복(Divide and Conquer)과 백트래킹

 

---

REVIEW

 

우선 무슨 알고리즘을 사용해야할지 개념이 떠오르는 게 없어 막연했다. 

반복적으로 해야할 동작을 쪼개어 손코딩을 해보았다.

 

패를 하나 선택한다 -> 비교할 패를 선택한다 -> 패의 뒷 숫자와 비교할 패의 앞숫자가 같은지 확인한다 -> 같지 않다면 뒤집어서 확인해 본다 -> 뒤집어서 같지 않다면 그 다음 패를 가지고 비교한다. 정도의 반복이 나올 것 같았다.

 

이에 따라 코드를 써내려 가다가, 우선 도미노를 담아둘 공간을 마련해야 겠다는 생각과, 틀렸을 때 디버깅이 조금 노가다스러워지겠다 생각이 들자 끈기없게 포기해버렸다.

 

무작정 지피티에게 질문했더니 관련 개념은 백트래킹이라고 알려주며 풀이 코드를 짜주었다.

고민을 세 번이라도, try를 세 번이라도 해본 뒤 지피티를 사용할 것 .. 명심!

---

CODE

using System;
using System.Collections.Generic;
using System.Linq;

public static class Dominoes
{
    public static bool CanChain(IEnumerable<(int, int)> dominoes)
    {
        // 도미노 리스트로 변환
        var dominoList = dominoes.ToList();

        // 도미노가 없으면 유효한 체인 (빈 체인은 항상 유효)
        if (!dominoList.Any()) return true;

        // 백트래킹을 이용해 체인 가능 여부 확인
        return CanFormChain(dominoList, new List<(int, int)>());
    }

    private static bool CanFormChain(List<(int, int)> remaining, List<(int, int)> chain)
    {
        // 기저 사례: 남은 도미노가 없으면 체인 유효성 검사
        if (!remaining.Any())
        {
            if (chain.Count == 0) return true; // 빈 체인
            return chain.First().Item1 == chain.Last().Item2; // 첫 번째와 마지막 도미노 점수 비교
        }

        // 남은 도미노를 하나씩 시도
        for (int i = 0; i < remaining.Count; i++)
        {
            var current = remaining[i];
            var nextRemaining = new List<(int, int)>(remaining);
            nextRemaining.RemoveAt(i);

            // 도미노를 뒤집지 않은 상태로 추가
            if (chain.Count == 0 || chain.Last().Item2 == current.Item1)
            {
                var newChain = new List<(int, int)>(chain) { current };
                if (CanFormChain(nextRemaining, newChain)) return true;
            }

            // 도미노를 뒤집은 상태로 추가
            var flipped = (current.Item2, current.Item1);
            if (chain.Count == 0 || chain.Last().Item2 == flipped.Item1)
            {
                var newChain = new List<(int, int)>(chain) { flipped };
                if (CanFormChain(nextRemaining, newChain)) return true;
            }
        }

        return false; // 유효한 체인을 찾을 수 없음
    }
}