본문 바로가기
백준일지

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

by 민지기il 2025. 4. 8.
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define MAX 5
using namespace std;

int answer;
bool select[8];
char ItoC[8] = {'A','C','F','J','M','N','R','T'};

void DFS(int cnt, char arr[], vector<string> data){
    if(cnt == 8)
    {
        for(int i=0; i<data.size(); i++)
        {
            char n1 = data[i][0];
            char n2 = data[i][2];
            char cond = data[i][3];
            int dist = data[i][4]-'0';
            dist++;
            
            int idx, iidx;
            idx = iidx = -1;
            for(int j=0; j<8; j++){
                if(arr[j] == n1) idx = j;
                if(arr[j] == n2) iidx = j;
                if(idx !=-1 && iidx !=-1) break;
            }
            if(cond == '=' && abs(idx-iidx) != dist) return;
            if(cond == '<' && abs(idx-iidx) >= dist) return;
            if(cond == '>' && abs(idx-iidx) <= dist) return;
        }
        answer++;
        return;
    }
    for(int i=0; i<8; i++)
    {
        if(select[i]==true) continue;
        select[i] = true;
        arr[cnt] = ItoC[i];
        DFS(cnt+1, arr, data);
        select[i] = false;
    }
}


int solution(int n, vector<string> data){
    fastio;
    char arr[8] = {NULL, };
    answer = 0;
    DFS(0, arr, data);
    return answer;
}

[참고]

https://yabmoons.tistory.com/459

[설명]

순열

https://yabmoons.tistory.com/100

#define MAX 5
using namespace std; 

int Arr[MAX];
bool Select[MAX];
vector<int> V; 

void Print(){    
	for (int i = 0; i < V.size(); i++)    {
    cout << V[i] << " ";    }    
    cout << endl;
} 

void DFS(int Cnt)
{    
	if (Cnt == 3)    
	{  
       Print();        
   	   return;    
	}     
    for (int i = 0; i < MAX; i++)    
    {        
    if (Select[i] == true) continue;        
    Select[i] = true;        
    V.push_back(Arr[i]);        
    DFS(Cnt + 1);        
    V.pop_back();        
    Select[i] = false;    
}} 

int main(void){    
	Arr[0] = 1;    
	Arr[1] = 2;    
	Arr[2] = 3;    
	Arr[3] = 4;    
	Arr[4] = 5;     
	DFS(0);
}

 

'백준일지' 카테고리의 다른 글

[백준] 2437번 저울  (0) 2025.04.10
[프로그래머스] 서버 증설  (0) 2025.04.09
[백준] 6497번 전력난  (0) 2025.04.07
[백준] 1781번 컵라면  (0) 2025.04.03
[백준] 1450번 냅색문제  (0) 2025.04.02