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

💡Summary

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

💡Idea

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

  • dfscnt==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;
}

좋은 웹페이지 즐겨찾기