프로그래머스 [2025 프로그래머스 코드챌린지 1차 예선 / 비밀 코드 해독](C++) -yes6686- 티스토리

프로그래머스 알고리즘 문제: 문제 해결을 위한 백트래킹

---

문제 설명:

n개의 번호 중 5개를 선택하는 조합을 생성하고, 주어진 조건을 만족하는 경우의 수를 세는 문제입니다. 특정 조건을 만족하는지 확인하기 위해, q 리스트에서 제시된 그룹과 ans 리스트에서 요구된 개수를 비교하여 정답을 도출해야 합니다.

---

문제 해결 코드

#include <string>
#include <vector>

using namespace std;

int visited[31];  // 방문 여부를 체크하는 배열
int arr[10][31];  // 특정 그룹의 포함 여부를 저장하는 배열
int c[11];  // 그룹의 조건값 저장
int answer = 0;  // 최종 정답 저장
int N;  // 전체 숫자의 개수
int qS;  // 그룹 개수

// 백트래킹 함수 (현재 선택한 개수 n과 시작점 d)
void bt(int d, int n) {
    if (n == 5) {  // 5개의 숫자를 선택한 경우
        bool check = true;
        
        for (int i = 0; i < qS; i++) {  
            int cnt = 0;
            for (int j = 1; j <= N; j++) {
                if (visited[j] == 1 && arr[i][j] == 1) cnt++;
            }
            if (cnt != c[i]) {  // 조건을 만족하지 않는 경우
                check = false;
                break;
            }
        }

        if (check) {
            answer++;  // 조건을 만족하면 카운트 증가
        }
        return;
    }
    
    // 백트래킹을 이용하여 조합 생성
    for (int i = d; i <= N; i++) {
        if (visited[i] == 0) { 
            visited[i] = 1;
            bt(i + 1, n + 1);
            visited[i] = 0;
        }
    }
}

int solution(int n, vector<vector<int>> q, vector<int> ans) {
    N = n;

    for (int i = 0; i < ans.size(); i++) {
        c[i] = ans[i];  // 조건값 저장
    }

    qS = q.size();  // 그룹 개수 저장

    for (int i = 0; i < qS; i++) {
        for (int j = 0; j < 5; j++) {
            arr[i][q[i][j]] = 1;  // 특정 그룹에 포함된 숫자 체크
        }
    }
    
    bt(1, 0);  // 백트래킹 시작
    
    return answer;
}

---

코드 설명

• 백트래킹을 이용한 조합 생성: 숫자 n개 중 5개를 선택하는 모든 경우를 탐색.
• 조건 검사: 선택된 조합이 주어진 q 그룹과 ans 개수를 만족하는지 확인.
• 배열 초기화: arr[i][j]를 사용하여 특정 숫자가 그룹 q[i]에 속하는지 여부를 저장.
• 재귀적 백트래킹: 방문 여부를 체크하면서 조합을 생성하고, 조건을 만족하면 answer 값을 증가.

---

실행 결과 예시

예제 입력:

n = 7
q = [[1, 2, 3, 4, 5], [2, 3, 6, 7, 1]]
ans = [3, 2]

예제 출력:

0

이 예제에서는 조건을 만족하는 조합이 총 3가지 경우가 존재합니다.

---

고려할 점 및 추가적인 접근

• 시간 복잡도: 조합을 생성하는 과정에서 최대 nC5개의 경우를 탐색해야 하므로 O(n^5)의 복잡도가 발생할 수 있음.
• 메모리 최적화: 불필요한 전역 변수 대신, vector를 활용하여 동적 메모리 할당 가능.
• 최적화 기법: 현재까지 선택된 숫자가 조건을 만족할 가능성이 없으면 가지치기 (Pruning) 기법을 적용하여 탐색량을 줄일 수 있음.