C# 역추적(Backtracking)으로 모바일 키패드 값의 모든 조합 구하기

복잡해 보이는 이 문제는 사실 더 작고 단순한 하위 문제(subproblem)들로 나누어 해결할 수 있습니다. 역추적(Backtracking) 기법의 핵심은 바로 여기에 있습니다. 하나의 큰 문제를 반복적으로 쪼개어 가장 단순한 형태까지 분해한 뒤, 각 단계에서 가능한 선택지를 하나씩 시도하고 결과를 누적하는 방식입니다.

접근 방식

이 문제는 다음과 같은 흐름으로 해결합니다.

1. 입력받은 숫자 문자열에서 첫 번째 자릿수를 하나씩 가져옵니다.
2. 해당 숫자에 매핑된 문자들을 딕셔너리(Map)에서 조회합니다. 예를 들어 '2'는 "abc", '3'은 "def"에 대응됩니다.
3. 조회된 각 문자를 현재까지 만든 문자열에 붙인 뒤, 남은 자릿수에 대해 재귀적으로 같은 과정을 반복합니다.
4. 처리할 자릿수가 더 이상 없으면 완성된 조합을 결과 목록에 추가합니다.

이렇게 하면 입력된 모든 자릿수 조합에 대해 가능한 문자열이 빠짐없이 생성됩니다.

예제 코드

using System;
using System.Collections.Generic;

namespace ConsoleApplication
{
    public class BackTracking
    {
        // 숫자별로 대응되는 키패드 문자 매핑
        private string GetKeyPadValueBasedOnInput(string digit)
        {
            var keypad = new Dictionary<string, string>
            {
                { "2", "abc" },
                { "3", "def" },
                { "4", "ghi" },
                { "5", "jkl" },
                { "6", "mno" },
                { "7", "pqrs" },
                { "8", "tuv" },
                { "9", "wxyz" }
            };
            return keypad.GetValueOrDefault(digit);
        }

        // 재귀적으로 모든 조합 탐색
        public void FindSequence(string currentList, string digits, List<string> output)
        {
            if (digits.Length == 0)
            {
                // 남은 자릿수가 없으면 완성된 조합 저장
                output.Add(currentList);
                return;
            }
            else
            {
                string digit = digits.Substring(0, 1);
                string letters = GetKeyPadValueBasedOnInput(digit);

                for (int i = 0; i < letters.Length; i++)
                {
                    char letter = letters[i];
                    // 현재 문자를 붙이고 나머지 자릿수에 대해 재귀 호출
                    FindSequence(currentList + letter, digits.Substring(1), output);
                }
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            BackTracking b = new BackTracking();
            List<string> output = new List<string>();

            b.FindSequence("", "34", output);

            foreach (var item in output)
            {
                Console.WriteLine(item);
            }
        }
    }
}

실행 결과

입력값 "34"에 대해 '3' → d, e, f / '4' → g, h, i가 매핑되므로 총 9개(3 × 3)의 조합이 출력됩니다.

dg
dh
di
eeg → eg
eh
ei
fg
fh
fi

정리

역추적 기법은 이처럼 선택 → 탐색 → 되돌아오기의 반복 구조로 동작합니다. 키패드 조합 생성뿐 아니라 N-Queen, 순열·조합 생성, 스도쿠 풀이 등 다양한 알고리즘 문제에 널리 활용되는 패턴이므로, 위 예제를 통해 재귀와 조합 탐색의 기본기를 익혀두면 큰 도움이 됩니다.