<Programmers> Lv2 DFS_단체사진 찍기 c++
5049 단어 programmersDFSkakaoalgorithmDFS
💡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; }
Author And Source
이 문제에 관하여(<Programmers> Lv2 DFS_단체사진 찍기 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Programmers-Lv2.-DFS단체사진-찍기-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)