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

 

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

코딩테스트 연습 - 단체사진 찍기

순열을 전부 구한 후, 조건에 따라 체크

#include <string>
#include <vector>
#include <iostream>
#include <cmath>

using namespace std;

int answer = 0;
bool* visited = new bool[8];

bool check(vector<string> data, string st) {
    for(string d : data) {
        int a = st.find(d[0]);
        int b = st.find(d[2]);
        char op = d[3];
        int num = d[4]-'0';
        
        // false를 먼저 리턴해야 함
        if (op == '=')
            if (!(abs((int)(a-b)) == num +1)) return false;
        else if (op == '>')
            if (!(abs((int)(a-b)) > num +1)) return false;
        else if (op == '<')
            if (!(abs((int)(a-b)) < num +1)) return false;
    }
    return true;
}

void dfs(int n, vector<string> data, char* li, int idx, string st){
    if (idx == 7) { // 8이면 시간 초과
        if(check(data, st)) {
            cout << st << "\n";
            answer++;
        }
        return;
    }
    
    for(int i=0; i<8; i++) {
        if(!visited[i]) {
            visited[i] = true;
            string str = st + li[i]; // 새 변수
            dfs(n, data, li, idx+1, str);
            visited[i] = false;
        }
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    answer = 0;
    char li[8] = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    
    for(int i=0; i<8; i++) visited[i] = false;
    
    dfs(n, data, li, 0, "");
    
    return answer;
}