프로그래머스 - 단체사진 찍기

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

프로그래머스

1. 특징

1) dfs or next_permutation

 

2. 구현 방법

dfs를 이용해서 가능한 순서를 모두 구하고, 그 순서가 조건에 맞는 지 확인한다. 

8! * 100 이므로 시간초과가 나지 않을 것이라 생각했다. 

 

3. 코드

#include <bits/stdc++.h>

using namespace std;
char str[8] = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'}; 
int vis[8];

int cnt;

void dfs(int cur, char ans[], vector<string> _data)
{
    if(cur == 8)
    {
        for(int i = 0; i < _data.size(); i++)
        {
            int f1 = 0; int f2 = 0;
            for(int j = 0; j < 8; j++)
            {
                if(ans[j] == _data[i][0]) f1 = j;
                else if(ans[j] == _data[i][2]) f2 = j;
            }
            
            char op = _data[i][3];
            int num = _data[i][4] - '0';
            
            if(op == '=' && abs(f1-f2) != num+1) return;
            else if(op == '>' && abs(f1-f2) <= num+1) return;
            else if(op == '<' && abs(f1-f2) >= num+1) return;
            
        }
        cnt++;
        return;
    }
    
    for(int i = 0; i < 8; i++)
    {
        if(vis[i] == 1) continue;
        vis[i] = 1;
        ans[cur] = str[i];
        dfs(cur+1, ans, _data);
        vis[i] = 0;
            
    }
}

int solution(int n, vector<string> data) {
    cnt = 0;
    char ans[8] = {NULL, };
    dfs(0, ans, data);
    return cnt;
}