Programmers[level 2] 단체사진 찍기

단체사진 찍기

• 문제 설명
  

• 입력 형식
  

• 출력 형식
  

• 예제 입출력
  

• 예제에 대한 설명
  

• 문제 풀이

인접한 영역들끼리 같은 색깔을 가지고 있다면, 방문 체크를 해주면서 탐색을 진행해주었다.
물론 정답을 찾기 위해서 탐색 하면서 탐색 중인 영역의 크기를 따로 Count 해 주었다.
영역의 갯수는, BFS함수가 호출되는 횟수와 동일하다. 예를 들어서,

1 1 0 2
1 0 0 2
0 3 3 0
0 3 3 0

위와 같은 맵이 존재할 때, 영역의 갯수는 3개 인데,
(0, 0)에 존재하는 '0'에 의해서 DFS탐색 한번 호출,
(0, 3)에 있는 '2'에 의해서 DFS탐색 한번 호출,
(2, 1)에 있는 '3'에 의해서 DFS탐색 한번 호출
총 3번의 BFS함수가 호출되어진다. 즉, BFS함수 호출 횟수가 영역의 갯수가 된다.

< DFS 재귀 호출 관련 보너스 팁>
i = [0, 1, 2, 3]라고 가장할 때, 가능한 경우의 수 432*1 = 24

경우의 수:
0123 1023 2013 3012
0132 1032 2031 3021
0213 1203 2103 3102
0231 1230 2130 3120
0312 1302 2301 3201
0321 1320 2310 3210

코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
int Answer;
bool Select[8] = {false};
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++){ // "N~F=0"
            char N1 = data[i][0];               // 본인(조건을 제시한 프렌즈) 
            char N2 = data[i][2];               // 상대
            char Cond = data[i][3];             // {=, <, >}
            int Dist = (data[i][4]-'0')+1;      // 거리 (정수로 변환)
            int Idx, IIdx;              	// Idx : 본인의 Arr 속 인덱스, IIdx : 상대의 Arr 속 인덱스
            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;
            }
            // 조건식이 유효하지 않으면 pass (경우의 수로 간주하지 않음, 8!중 겨우 하나의 8단계 pass 됨)
            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); // Cnt = 0 -> i=0 -> DFS(1, Arr, Data) ->38 Select[i] = False -> i=1 (For문의 정의 ) -> Arr[0]=ItoC[1] -> DFS(1, Arr, Data) (i=1인 버전) 
        Select[i] = false;
    }                                               
}
 
int solution(int n, vector<string> data){
    char Arr[8] = { NULL, };
    Answer = 0;                // 단계(Cnt)
    DFS(0, Arr, data);      // 0단계 DFS를 1번 = 1단계 DFS를 8번 = 2단계 DFS를 8*7번 = 3단계 DFS를 8*7*6번 = ... = 8단계 DFS를 8!번
    return Answer;          // 1단계 DFS를 1번 = 2단계 DFS를 7번 (왜? 아까 사용했던 i는 또 안쓸라고) = ... = 8단계 DFS를 7!번
}

int main() {
    int n = 2;
    vector<string> data;
    data.push_back("N~F=0");
    data.push_back("R~T>2");
    cout << solution(2, data);

    return 0;
}