<Programmers> Lv2 DFS_단체사진 찍기 c++

💡Summary

• data 원소는 다섯 글자로 구성된 문자열
• 첫 번째 글자와 세 번째 글자는 프렌즈들의 알파벳 앞글자
• 두 번째 글자는 항상 ~
• 네 번째 글자는 {=, <, >}중 하나이고 프렌즈들 간 거리가 같음, 미만, 초과를 의미
• 다섯 번째 글자는 0이상 6이하의 정수 문자형이며 각 거리를 의미한다

💡Idea

• 먼저 8명의 프렌즈들이 한 줄로 서는 경우의 수를 생각한다
  경우의 수는 8!이며 DFS를 이용한 순열의 방법으로 모든 경우의 수를 구한다
• e.g. R~T>2 라는 뜻은 R과 T사이에 프렌즈 3명 이상이 있다는 말이고, 둘 사이의 거리는 3이상이라는 뜻이다. 그렇다면 N~F=0 이라는 뜻은 N과 F가 붙어있다는 뜻이고, 둘 사이 거리가 1이라는 뜻이다.

✏️1. Initialize

• 8명이 일자로 서는 경우의 수를 구하기 위해 몇 가지 변수를 선언한다

char arr[8]={NULL, };
bool selected[8];
char names[8]={'A','C','F','J','M','N','R','T'};

• arr[]에 프렌즈들이 일자로 섰을 때 순서대로 저장된다
• selected에는 i번 째 프렌즈가 이미 선택되었는지, 아닌지를 저장한다

✏️2. DFS

• dfs는 cnt==8 이 되었을 때, 즉 모든 프렌즈들이 일자로 섰을 때 data조건에 충족하는지 검사하고, 그렇지 않다면 계속 한 명씩 선택해 세우는 과정을 반복
• if (cnt!=8)

for (int i=0; i<8; i++) {
  if (selected[i]==true) continue;
  selected[i]=true;
  arr[cnt]=names[i];
  dfs (cnt+1, arr, data);
  selected[i]=false;
}

• if (cnt==8)
• 모든 data조건을 탐색하며 거리 조건이 맞는지 확인한다
• 다섯 글자로 구성된 문자열을 분해해서 저장

char f1=data[i][0]; // 첫 번째 프렌즈
char f2=data[i][2]; // 두 번째 프렌즈
char sign=data[i][3]; // 거리 조건 {=, <, >}
int dist=data[i][4]-'0'; 
dist++; //프렌즈간 거리

• 각 프렌즈의 위치를 f1_x, f2_x에 저장

int f1_x, f2_x;
for (int j=0; j<8; j++) {
	if (f1==arr[j]) f1_x=j;
	else if (f2==arr[j]) f2_x=j;
}

• 각 프렌즈간 거리를 구하고, 거리 조건에 부합하는지 확인

if (sign=='=' && abs(f1_x-f2_x)!=dist) return;
if (sign=='>' && abs(f1_x-f2_x)<=dist) return;
if (sign=='<' && abs(f1_x-f2_x)>=dist) return;

• 거리 조건에 부합하면 answer++

🔖Source Code

#include <string>
#include <vector>

using namespace std;

int answer;
bool selected[8];
char names[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 f1=data[i][0];
            char f2=data[i][2];
            char sign=data[i][3];
            int dist=data[i][4]-'0';
            dist++;
          
            int f1_x, f2_x;
            for (int j=0; j<8; j++) {
                if (f1==arr[j]) f1_x=j;
                else if (f2==arr[j]) f2_x=j;
            }
          
            if (sign=='=' && abs(f1_x-f2_x)!=dist) return;
            if (sign=='>' && abs(f1_x-f2_x)<=dist) return;
            if (sign=='<' && abs(f1_x-f2_x)>=dist) return;
        }
        answer++;
        return ;
    }
    for (int i=0; i<8; i++) {
        if (selected[i]==true) continue;
        selected[i]=true;
        arr[cnt]=names[i];
        dfs (cnt+1, arr, data);
        selected[i]=false;
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    answer=0;
    char arr[8]={NULL, };
    dfs(0, arr, data);
    return answer;
}