C#에서 백트래킹(backtracking) 기법을 활용하면 주어진 숫자 k에 대해 여는 괄호 '{'와 닫는 괄호 '}'로 만들 수 있는 모든 유효한 조합을 효율적으로 찾을 수 있습니다. 이 문제는 재귀 호출을 통해 가능한 모든 경우를 탐색하되, 유효하지 않은 경로는 미리 잘라내는(backtrack) 방식으로 해결합니다.
알고리즘 접근 방식
백트래킹 함수를 생성하고, 다음 규칙에 따라 현재 문자열을 갱신해 나갑니다.
- 아직 배치할 여는 괄호가 남아 있다면(여는 괄호 개수 < n) 여는 괄호 '{'를 추가할 수 있습니다.
- 닫는 괄호의 개수가 여는 괄호보다 적다면 닫는 괄호 '}'를 추가할 수 있습니다. 즉, 닫는 괄호가 여는 괄호의 개수를 초과하지 않도록 합니다.
- 현재 문자열의 길이가 2*n과 같아지면 완성된 조합을 결과 배열에 추가합니다.
배치된 '{'와 '}'의 개수만 추적하면 되므로 구현이 비교적 간단합니다. 각 단계에서 두 가지 선택지(여는 괄호 추가 또는 닫는 괄호 추가)를 재귀적으로 시도하면서 유효한 조합만 남기는 원리입니다.
예제 코드
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace ConsoleApplication{
public class BackTracking{
public void Brackets(){
char[] arr = new char[4];
FindSequence(arr, 0, 2, 0, 0);
}
private static void FindSequence(char[] arr, int index, int N, int openBracket, int closeBracket){
if (closeBracket == N){
StringBuilder s = new StringBuilder();
for (int i = 0; i < arr.Length; i++){
s.Append(arr[i]);
}
Console.WriteLine(s);
s = null;
return;
}
else{
if (openBracket > closeBracket){
arr[index] = '}';
FindSequence(arr, index + 1, N, openBracket, closeBracket + 1);
}
if (openBracket < N){
arr[index] = '{';
FindSequence(arr, index + 1, N, openBracket + 1, closeBracket);
}
}
}
}
class Program{
static void Main(string[] args){
BackTracking b = new BackTracking();
b.Brackets();
}
}
}코드 설명
위 예제에서는 n = 2인 경우를 처리합니다. FindSequence 메서드는 현재 인덱스, 열린 괄호 수(openBracket), 닫힌 괄호 수(closeBracket)를 매개변수로 받아 재귀적으로 동작합니다. 닫힌 괄호의 개수가 N에 도달하면 하나의 유효한 조합이 완성된 것이므로 문자열을 출력하고 종료합니다. 그렇지 않으면 앞서 설명한 두 가지 조건을 검사하여 각각 여는 괄호와 닫는 괄호를 추가하며 재귀 호출을 진행합니다.
실행 결과
{}{}
{{}}n = 2일 때 생성 가능한 모든 유효한 괄호 조합은 위와 같이 총 2가지입니다. 일반적으로 n쌍의 괄호로 만들 수 있는 유효한 조합의 개수는 카탈란 수(Catalan number)와 같으며, n = 2일 때는 2, n = 3일 때는 5가지 조합이 나옵니다.