[C++] 프로그래머스 단체사진 찍기

https://school.programmers.co.kr/learn/courses/30/lessons/1835

프로그래머스

풀이

중복 없이 가능한 모든 경우의 수(줄 세우기)에 대해 조건을 검사하는 DFS를 구현했다.

check 함수는 카카오프렌즈 줄세우기가 끝나면 주어진 조건들에 대해 모두 통과 되는지 확인한다.

모든 조건에 대해 check하는 과정에서 누적합 변수를 사용해 검사하는 코드(누적합 == cpy_data.size()) 를 사용했더니 시간 초과가 났다.

flag 변수 를 사용해서 중간에 break를 걸어두니 통과됐다.

#include <string>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;

vector<string> element={"A", "C", "F", "J", "M", "N", "R", "T"};
vector<string> cpy_data;
int visited[8];
int cnt;

int check(int idx1, int idx2, string op, string num){
    int n = stoi(num);
    if (op=="="){
        if (abs(idx1-idx2)-1 == n) return 1;
        return 0;
    }
    if (op=="<"){
        if (abs(idx1-idx2)-1<n) return 1;
        return 0;
    }
    if (op==">"){
        if (abs(idx1-idx2)-1>n) return 1;
        return 0;
    }
}

void dfs(vector<string>& ch){
    if (ch.size()==8){
        bool flag=true;
        for (int i=0; i<cpy_data.size(); i++){
            string a1 = cpy_data[i].substr(0, 1);
            string a2 = cpy_data[i].substr(2, 1);
            string op = cpy_data[i].substr(3, 1);
            string num = cpy_data[i].substr(4);
            // 인덱스 뽑기
            int idx1=0, idx2=0;
            for (int j=0; j<ch.size(); j++){
                if (a1 == ch[j]) { idx1=j; }
                if (a2 == ch[j]) { idx2=j; }
            }
            // 검사
            if (!check(idx1, idx2, op, num)) {
                flag=false;
                break;
            }
        }
        if (flag) cnt++;
    }
    for (int i=0; i<8; i++){
        if (!visited[i]){
            visited[i]=1;
            ch.push_back(element[i]);
            dfs(ch);
            ch.pop_back();
            visited[i]=0;
        }
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    int answer=0;
    cpy_data=data;
    vector<string> c;
    memset(visited, 0, sizeof(visited));
    cnt=0;
    dfs(c);
    answer=cnt;
    return answer;
}