[C++로 풀이] 단체사진 찍기 (경우의 수, 순열, DFS, next_permutation) ⭐⭐

Date: 2021.02.10 Updated: 2021.02.10

카테고리: Programmers

📌 단체사진 찍기

난이도 ⭐⭐

🚀 문제

✈ 예제 1 번의 답이 3648 인 이유

N과 F는 딱 붙어 있어야 하고
R과 T는 간격은 2 초과여야 한다.(간격은 3, 4, 5, 6 이 될 수 있음)

💙은 R과 T를 포함한 R과 T사이 구간 프렌즈들, 💛 은 N도 F도 아니고 R과 T 사이에 있지 않은 구간에 속한 프렌즈들이라고 가정하겠다. 💚💚 는 NF (혹은 FN). 하트 하나 당 하나의 프렌즈다!

R과 T의 간격이 3 일 때
- 💛💛💛💙💙💙💙💙
  - R과 T 사이에 N과 F가 “있는” 경우 👉 2! * 2! * 4! * 2 * 4 = 768
    - 순서만 고려
      - 2! : R과 T끼리의 순열. (R💙💙💙T), (T💙💙💙R) 이렇게 2 가지.
      - 2! : N과 F끼리의 순열. (NF), (FN) 이렇게 2가지.
      - 4! : R,T,N,F 를 제외한 나머지 4명의 프렌즈들끼리의 순열.
    - 자리만 고려
      - 2 : R,T를 제외한 R,T 사이의 💙💙💙 내에 💚💚 가 자리할 수 있는 가짓 수는 2가지다.
        
        (💚💚💙, 💙💚💚)
      - 4 : ^💛^💛^💛^ 이렇게 4개의 ^ 부분에 💙💙💙💙💙 가 자리할 수 있다.
  - R과 T 사이에 N과 F가 “없는” 경우 👉 2! * 2! * 4! * 3! = 576
    - 순서만 고려
      - 2! : R과 T끼리의 순열. (R💙💙💙T), (T💙💙💙R) 이렇게 2 가지.
      - 2! : N과 F끼리의 순열. (NF), (FN) 이렇게 2가지.
      - 4! : R,T,N,F 를 제외한 나머지 4명의 프렌즈들끼리의 순열.
    - 자리만 고려
      - 3! : [💛], [💚💚], [💙💙💙💙💙] 이렇게 3 가지 “자리”들끼리의 순열은 3! 가지.
R과 T의 간격이 4 일 때
- 💛💛💙💙💙💙💙💙
  - R과 T 사이에 N과 F가 “있는” 경우 👉 2! * 2! * 4! * 3 * 3 = 864
    - 순서만 고려
      - 2! : R과 T끼리의 순열. (R💙💙💙💙T), (T💙💙💙💙R) 이렇게 2 가지.
      - 2! : N과 F끼리의 순열. (NF), (FN) 이렇게 2가지.
      - 4! : R,T,N,F 를 제외한 나머지 4명의 프렌즈들끼리의 순열.
    - 자리만 고려
      - 3 : R,T를 제외한 R,T 사이의 💙💙💙💙 내에 💚💚 가 자리할 수 있는 가짓 수는 3 가지다.
        
        (💚💚💙💙, 💙💚💚💙, 💙💙💚💚)
      - 3 : ^💛^💛^ 이렇게 3 개의 ^ 부분에 💙💙💙💙💙💙 가 자리할 수 있다.
  - R과 T 사이에 N과 F가 “없는” 경우 👉 2! * 2! * 4! * 2! = 192
    - 순서만 고려
      - 2! : R과 T끼리의 순열. (R💙💙💙T), (T💙💙💙R) 이렇게 2 가지.
      - 2! : N과 F끼리의 순열. (NF), (FN) 이렇게 2가지.
      - 4! : R,T,N,F 를 제외한 나머지 4명의 프렌즈들끼리의 순열.
    - 자리만 고려
      - 2! : [💚💚], [💙💙💙💙💙💙] 이렇게 2 가지 “자리”들끼리의 순열은 2! 가지.
R과 T의 간격이 5 일 때
- 💛💙💙💙💙💙💙💙
  - R과 T 사이에 N과 F가 “있는” 경우 👉 2! * 2! * 4! * 4 * 2 = 768
    - 순서만 고려
      - 2! : R과 T끼리의 순열. (R💙💙💙💙💙T), (T💙💙💙💙💙R) 이렇게 2 가지.
      - 2! : N과 F끼리의 순열. (NF), (FN) 이렇게 2가지.
      - 4! : R,T,N,F 를 제외한 나머지 4명의 프렌즈들끼리의 순열.
    - 자리만 고려
      - 4 : R,T를 제외한 R,T 사이의 💙💙💙💙💙 내에 💚💚 가 자리할 수 있는 가짓 수는 4 가지다.
        
        (💚💚💙💙💙, 💙💚💚💙💙, 💙💙💚💚💙, 💙💙💙💚💚)
      - 2 : ^💛^ 이렇게 2 개의 ^ 부분에 💙💙💙💙💙💙💙 가 자리할 수 있다.
  - R과 T 사이에 N과 F가 “없는” 경우 👉 0. 없다! R과 T가 아닌 구간은 길이가 1 이 될 수 밖에 없어서 N과 F는 불가피하게 R과 T 사이에 들어갈 수 밖에 없다.
R과 T의 간격이 6 일 때
- 💙💙💙💙💙💙💙💙
  - R과 T 사이에 N과 F가 “있는” 경우 👉 2! * 2! * 4! * 5 * 1 = 480
    - 순서만 고려
      - 2! : R과 T끼리의 순열. (R💙💙💙💙💙💙T), (T💙💙💙💙💙💙R) 이렇게 2 가지.
      - 2! : N과 F끼리의 순열. (NF), (FN) 이렇게 2가지.
      - 4! : R,T,N,F 를 제외한 나머지 4명의 프렌즈들끼리의 순열.
    - 자리만 고려
      - 5 : R,T를 제외한 R,T 사이의 💙💙💙💙💙💙 내에 💚💚 가 자리할 수 있는 가짓 수는 5 가지다.
        
        (💚💚💙💙💙💙, 💙💚💚💙💙💙, 💙💙💚💚💙💙, 💙💙💙💚💚💙, 💙💙💙💙💚💚)
      - 1 : 💙💙💙💙💙💙💙💙 가 자리할 수 있는 경우는 1 가지.
  - R과 T 사이에 N과 F가 “없는” 경우 👉 0. 없다! R과 T가 아닌 구간은 없기 때문에 N과 F는 불가피하게 R과 T 사이에 들어갈 수 밖에 없다.

밑줄 친 것들만 더하면 768 + 576 + 864 + 192 + 768 + 480 = 3648 이 된다.

🚀 내 풀이

위 예제는 n이 2 밖에 안되어 2 가지만 보면 됐지만 n이 여러 개라면 어떻게 경우의 수를 계산할지 갑갑했다. 다행히도 프렌즈가 8 명밖에 없고 n도 100 이 최대라 8명의 프렌즈의 모든 순열을 전부 구한 후 이 순열이 data 조건들에 모두 만족하는 순열인지 이렇게 검사해도 시간 초과 나지 않는다. 8! * 100 = 4,032,000 최대 연산이 이 정도기 때문에 괜찮다. 입력 크기가 그리 크지 않다면 그냥 모든 순열과 모든 조합을 다 구한 후 일일이 검사해도 괜찮다. 배제하지 말자!!

✈ next_permutation 사용하여 순열 구한 풀이 ⭕

참고
- next_permutation 로 순열 구하는 방법
- next_permutation 로 조합 구하는 방법

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<string> data) {
    int answer = 0;
    string friends = "ACFJMNRT";
    
    do{
        bool flag = true;
        for(int i = 0; i < n; ++i){
            int friend1_idx = 0;
            int friend2_idx = 0;
            for(int j = 0; j < friends.length(); ++j){
                if (friends[j] == data[i][0])
                    friend1_idx = j;
                if (friends[j] == data[i][2])
                    friend2_idx = j;
            }
            
            int gap = max(friend1_idx - friend2_idx, friend2_idx - friend1_idx) - 1;
            if (data[i][3] == '='){
                if (gap != data[i][4] - '0'){
                    flag = false;
                    break;
                }
            }
            if (data[i][3] == '>'){
                if (gap <= data[i][4] - '0'){
                    flag = false;
                    break;
                }
            }
            if (data[i][3] == '<'){
                if (gap >= data[i][4] - '0'){
                    flag = false;
                    break;
                }
            }
        }
        if (flag == true) answer++; 
    }while(next_permutation(friends.begin(), friends.end()));
    
    return answer;
}

8 명의 프렌즈를 firends 문자열로 관리했고 이걸 next_permutation 을 통해 정렬하여 다음 순열로 원소들의 자리를 바꿔나갈 것이다.
- 초기 상태는 “ACFJMNRT” 로 이 자체로 오름차순 정렬이 되어 있기 때문에 모든 순열을 구할 수 있는 초기값이 된다.
그냥 friends의 모든 순열을 검사하여 해당 순열마다 또 모든 data 문자열들을 검사하여 조건에 모두 부합하는지 검사하면 된다.
- data 문자열의 모든 조건을 위반하지 않은 순열이라면 answer를 1 증가시킨다.

✈ DFS 사용하여 순열 구한 풀이 ⭕

void DFS(int& answer, vector<string>& data, string& friends, string perm, vector<bool> checked, int depth) {
    if (depth == friends.length()) {
        bool flag = true;
        for (int i = 0; i < data.size(); ++i) {
            int friend1_idx = 0;
            int friend2_idx = 0;
            for (int j = 0; j < perm.length(); ++j) {
                if (perm[j] == data[i][0])
                    friend1_idx = j;
                if (perm[j] == data[i][2])
                    friend2_idx = j;
            }

            int gap = abs(friend1_idx - friend2_idx) - 1;
            if (data[i][3] == '=') {
                if (gap != data[i][4] - '0') {
                    flag = false;
                    break;
                }
            }
            if (data[i][3] == '>') {
                if (gap <= data[i][4] - '0') {
                    flag = false;
                    break;
                }
            }
            if (data[i][3] == '<') {
                if (gap >= data[i][4] - '0') {
                    flag = false;
                    break;
                }
            }
        }
        if (flag == true) answer++;

        return;
    }

    for (int i = 0; i < friends.length(); ++i) {
        if (checked[i] == false) {
            checked[i] = true;
            perm[depth] = friends[i];
            DFS(answer, data, friends, perm, checked, depth + 1);
            checked[i] = false;
        }
    }
}

int solution(int n, vector<string> data) {
    int answer = 0;
    string friends = "ACFJMNRT";
    vector<bool> checked(friends.length(), false);
    string perm;
    perm.resize(friends.length());
    DFS(answer, data, friends, perm, checked, 0);

    return answer;
}

순열을 위와 같이 DFS 로 구할 수도 있다. perm에다가 순열을 만들어 나간다. if (depth == friends.length()) 에 도달했다면 다음 순열이 perm에 완성되었다는 것이므로 해당 순열이 data 모든 조건을 만족하는지 검사한다. 이 때 리턴하고 한 단계 빠져나오면 된다.

조합
- “012” 라는 조합을 완성했다면 “02” 로 시작하는 조합을 만들 땐 그 뒤에 “1”은 절대 등장할 수 없다.
순열
- 조합과 달리 순열은 “012” 라는 순열을 완성했다면 “02” 로 시작하는 순열을 만들 때 다시 “1”이 등장할 수 있다. “021” 가능
  - 따라서 DFS 로 순열을 구할 땐 DFS 끝난 후, 즉 순열 하나를 완성 한 후! 방문 체크를 다시 해제해주어야 한다. 하나의 순열을 만들어나갈 땐 재방문 불가능하지만, 아예 다른 순열을 만들 땐 재방문이 가능하다.

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

공부하는 식빵맘 👱‍♀️