[Algorithm] Greedy+BFS+Zerosum Problem

해당 문제는 Greedy+BFS+Zerosum Problem의 조합을 통해 답을 추출해내는 문제이다.

해당 문제는 농도를 계산하는 문제로 어떻게 효율적으로 제로섬을 만들어낼 것인가에서 고민은 출발하였다.

왜냐하면 입력값의 범위가 20만개였기 때문이었다. 하지만, 입력값의 범위를 0~1000, 즉 1001개로 중복제거를 통해 줄일 수 있었고, BFS를 돌리기 위해 필요한 Cut the Branch 작업이 필요했다.

이 부분은 resultMap라는 1차원 배열을 통해 쉽게 해결할 수 있었다.

다음 아래의 소스는 문제를 해결한 소스코드이다.

 

/*
사용언어 : CPP
작성일자 : 2017.06.20(화)
*/
#define _CRT_SECURE_NO_WARNINGS
 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
 
#define MAX 1010
 
using namespace std;
typedef struct {
    int val, level;
}forQ; //구조체 forQ는 BFS를 위해 사용한다. value와 level로 이루어져 있다.
int T, N, M; //case, Needs, Number of Base
int A[MAX], A1[MAX], A2[MAX], CNT[2]; // CNT[0] : use A1, CNT[1] : use A2
int resultMap[MAX*2], Result;
queue <forQ> Q;
 
//func
int proc();//BFS처리를 위한 사용자 정의 함수
void clearQ(queue <forQ> &clear);//Queue를 초기화하기 위한 사용자 정의 함수
 
int main() {
    //freopen("./sample_input.txt", "r", stdin);//입력을 파일입출력을 통해서 처리함.
    scanf("%d", &T);
    for (int ii = 1; ii <= T; ii++) {
        //input
        //입력 처리부
        int tempBase, flag=0;
        scanf("%d%d", &N, &M);
        for (int i = 0; i < M; i++) {
            scanf("%d", &tempBase);
            if (A[tempBase] == 0) {
                A[tempBase]++;
                tempBase = N - tempBase;
                if (tempBase == 0) { //1번에 농도를 맞출 수 있다면, flag를 1로 표시해줌.
                    flag = 1;
                }
                if (tempBase > 0) { //N을 기준으로 N-tempBase 연산을 하였을때, 양수라면 A1
                    A1[CNT[0]++] = tempBase;
                }
                else {//아니면 A2
                    A2[CNT[1]++] = tempBase;
                }
            }
        }
        //proc & print
        if (flag == 1) { //1번에 농도를 맞출 수 있음
            printf("#%d 1\n", ii);
        }
        else if (CNT[0] == 0 || CNT[1] == 0) { //양수만 존재하거나, 음수만 존재한다면 값을 도출할 수 없음
            printf("#%d -1\n", ii);
        }
        else { //BFS 연산결과 출력
            Result = proc();
            printf("#%d %d\n", ii, Result);
        }
 
        //init
        //사용한 변수들에 대한 초기화 작업
        memset(A, 0, sizeof(int)*MAX);
        memset(A1, 0, sizeof(int)*MAX);
        memset(A2, 0, sizeof(int)*MAX);
        memset(resultMap, 0, sizeof(int)*MAX*2);
        CNT[0] = 0; CNT[1] = 0;
        clearQ(Q);
    }
    return 0;
}
 
int proc() {
    //Queue를 위한 구조체 : forQ(val, level)
    //해당 함수에서 사용되는 resultMap은 BFS를 하면서 
    //하위레벨 혹은 동등레벨에서 똑같은 연산을 반복처리하지 않기위해 표시해주는 역할
    //메모라이제이션
    forQ forQTemp;
 
    //초기 Tree root를 BFS처리하기 전 PUSH
    for (int i = 0; i < CNT[0]; i++) {
        forQTemp.val = A1[i];
        forQTemp.level = 1;
        Q.push(forQTemp);
    }
    //BFS처리
    while(1) {
        forQ temp = Q.front();
        Q.pop();
        //무엇(양수, 음수)을 선택하느냐 => Greedy
        if (temp.val > 0) { //양수면 음수배열에서 Search
            for (int i = 0; i < CNT[1]; i++) {
                forQ k;
                k.val = temp.val + A2[i];
                if (k.val == 0) return temp.level + 1;
                if (resultMap[MAX + k.val] == 0) { //앞에서 처리한적이 없다면, Q에 연산결과 저장
                    resultMap[MAX + k.val] = 1;
                    k.level = temp.level + 1;
                    Q.push(k);
                }
            }
        }
        else if (temp.val < 0) { //음수면 양수배열에서 Search
            for (int i = 0; i < CNT[0]; i++) {
                forQ k;
                k.val = temp.val + A1[i];
                if (k.val == 0) return temp.level + 1;
                if (resultMap[MAX + k.val] == 0) { //앞에서 처리한적이 없다면, Q에 연산결과 저장
                    resultMap[MAX + k.val] = 1;
                    k.level = temp.level + 1;
                    Q.push(k);
                }
            }
        }
        
    }
}
 
void clearQ(queue <forQ> &clear) {
    queue <forQ> forClear;
    clear = forClear;
}