C++로 풀어보는 성냥개비 정사각형 만들기 문제

안데르센 동화 속 '성냥팔이 소녀'를 떠올려 봅시다. 소녀가 가진 성냥개비의 개수와 길이를 정확히 알고 있다면, 이 성냥개비를 전부 사용하여 하나의 정사각형을 만들 수 있는 방법을 찾아야 합니다. 단, 성냥개비를 부러뜨릴 수는 없고 서로 이어 붙일 수만 있으며, 각 성냥개비는 정확히 한 번씩 사용해야 합니다.

입력으로는 소녀가 가진 성냥개비들의 길이가 주어지고, 출력으로는 모든 성냥개비를 사용해 정사각형을 만들 수 있는지 여부(true 또는 false)를 반환해야 합니다. 예를 들어 입력이 [1,1,2,2,2]라면 답은 true입니다. 한 변의 길이가 2인 정사각형을 만들되, 한 변에는 길이 1짜리 성냥개비 두 개를 이어 붙이면 되기 때문입니다.

문제 해결 접근 방법

이 문제는 백트래킹(backtracking) 기법을 활용해 해결할 수 있습니다. 단계별로 살펴보겠습니다.

solve()라는 재귀 함수를 정의합니다. 이 함수는 현재 인덱스(idx), 네 변의 길이를 저장하는 배열(sums), 목표 길이(target), 성냥개비 배열(nums)을 매개변수로 받습니다.
idx가 nums의 크기 이상이라면(모든 성냥개비를 배치했다면)
- sums[0], sums[1], sums[2]가 모두 target과 같으면 true를 반환합니다.
i를 0부터 3까지 반복합니다.
- sums[i] + nums[idx] > target이면 해당 변에 더 이상 넣을 수 없으므로 다음 반복으로 건너뜁니다.
- sums[i] := sums[i] + nums[idx]
- solve(idx + 1, sums, target, nums)가 true이면 true를 반환합니다.
- 그렇지 않으면 sums[i] := sums[i] - nums[idx]로 되돌립니다(백트래킹).
모든 경우를 시도했는데도 실패하면 false를 반환합니다.

메인 함수(makesquare) 처리 과정

nums가 비어 있으면 false를 반환합니다.
x := 0으로 초기화한 뒤, 모든 성냥개비 길이의 합을 구합니다.
x가 4로 나누어 떨어지지 않으면 false를 반환합니다. 정사각형의 네 변 길이가 같아야 하므로 총합이 4의 배수가 아니면 애초에 불가능하기 때문입니다.
nums 배열을 내림차순으로 정렬합니다. 긴 성냥개비부터 먼저 배치하면 조건에 맞지 않는 경우를 빠르게 걸러낼 수 있어 탐색 범위가 크게 줄어듭니다.
크기가 4인 sums 배열을 만듭니다.
solve(0, sums, x/4, nums)의 결과를 반환합니다.

다음 구현 예시를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool solve(int idx, vector <int>& sums, int target, vector <int>& nums){
      if(idx >= nums.size()){
         return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == target;
      }
      for(int i = 0; i < 4; i++){
         if(sums[i] + nums[idx] > target)continue;
         sums[i] += nums[idx];
         if(solve(idx + 1, sums, target, nums)) return true;
         sums[i] -= nums[idx];
      }
      return false;
   }
   bool makesquare(vector<int>& nums) {
      if(nums.size() == 0) return false;
      int x = 0;
      for(int i = 0; i < nums.size(); i++){
         x += nums[i];
      }
      if(x % 4) return false;
      sort(nums.rbegin(), nums.rend());
      vector <int> sum(4);
      return solve(0, sum,x / 4, nums);
   }
};
main(){
   vector<int> v = {1,1,2,2,2};
   Solution ob;
   cout << (ob.makesquare(v));
}

입력

[1,1,2,2,2]