[C++][프로그래머스] 단체사진 찍기

프로그래머스

 

📄 문제

가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 달라 어떤 순서로 설지 정하는데 시간이 오래 걸렸다. 네오는 프로도와 나란히 서기를 원했고, 튜브가 뿜은 불을 맞은 적이 있던 라이언은 튜브에게서 적어도 세 칸 이상 떨어져서 서기를 원했다. 사진을 찍고 나서 돌아오는 길에, 무지는 모두가 원하는 조건을 만족하면서도 다르게 서는 방법이 있지 않았을까 생각해보게 되었다. 각 프렌즈가 원하는 조건을 입력으로 받았을 때 모든 조건을 만족할 수 있도록 서는 경우의 수를 계산하는 프로그램을 작성해보자.

 

📝 풀이

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

vector<bool> ch; // DFS에서 해당 원소를 사용했는가
vector<int> sel; // n번째에서 몇번 값을 사용하는가
string characters; // 캐릭터 배열
int cnt; // 사용할 개수 (캐릭터는 8개)
int answer; // 정답 누적

bool checkValid(vector<string>& data, map<char, int>& m)
{
    for(string s : data)
    {
        // 두 캐릭터 사이의 간격
        int dist = abs(m[s[0]] - m[s[2]]) - 1;
        
        // 요구 숫자
        int num = s[4] - '0';
                
        // 요구 조건
        switch(s[3])
        {
            case '=': // 간격이 같은경우?
            {
                // 간격이 다르면 false
                if(dist != num)
                    return false;
                break;
            }
            case '<': // 간격이 미만?
            {
                // 간격이 이상이면 false
                if(dist >= num)
                    return false;
                break;
            }
            case '>': // 간격이 초과?
            {
                // 간격이 이하이면 false
                if(dist <= num)
                    return false;                
                break;
            }                
        }
    }
    
    return true;
}

void DFS(int n, vector<string>& data)
{
    // 모두 선택했다면?
    if(n == cnt)
    {
        // map에 해당 캐릭터의 위치를 저장
        map<char, int> m;
        for(int i = 0; i < cnt; ++i)
            m[characters[sel[i]]] = i;
        
        // 해당 캐릭터 조합이 data 조건을 모두 만족한다면, ++answer;
        if(checkValid(data, m))
            ++answer;
    }
    else
    {
        for(int i = 0; i < cnt; ++i)
        {
            if(!ch[i])
            {
                sel[n] = i;
                ch[i] = true;
                DFS(n + 1, data);
                ch[i] = false;
            }
        }
    }
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    
    characters = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    ch = vector<bool>(8, false);
    sel = vector<int>(8, -1);
    answer = 0;
    cnt = 8;
    DFS(0, data);
    
    return answer;
}

• DFS와 map을 이용하여 문제를 해결하였습니다.
• DFS를 이용하여 캐릭터 8개의 가능한 모든 배치 순열을 구합니다.
• 하나의 캐릭터 조합이 나왔다면, map에 해당 캐릭터 글자를 기반으로 위치를 저장합니다. 이 과정은 조건계산에서 위치값을 빠르게 찾기 위해 사용합니다.
• checkValid 함수에서 data의 글자 규칙을 기반으로 필요한 요소들을 추출한 후 계산합니다.
• m[char]의 값은 현재 해당 캐릭터의 위치로, dist를 구할 수 있습니다.
• = < > 의 조건에 맞게 거짓이 되는 return false를 적은 후, 모든 조건을 통과하였다면 return true와 함께 answer을 1씩 올려줍니다. 

 

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

using namespace std;

vector<bool> ch; // DFS에서 해당 원소를 사용했는가
vector<int> sel; // n번째에서 몇번 값을 사용하는가
string characters; // 캐릭터 배열
int cnt; // 사용할 개수 (캐릭터는 8개)
int answer; // 정답 누적

bool checkValid(vector<string>& data, map<char, int>& m)
{
    for(string s : data)
    {
        // 두 캐릭터 사이의 간격
        int dist = abs(m[s[0]] - m[s[2]]) - 1;
        
        // 요구 숫자
        int num = s[4] - '0';
                
        // 요구 조건
        switch(s[3])
        {
            case '=': // 간격이 같은경우?
            {
                // 간격이 다르면 false
                if(dist != num)
                    return false;
                break;
            }
            case '<': // 간격이 미만?
            {
                // 간격이 이상이면 false
                if(dist >= num)
                    return false;
                break;
            }
            case '>': // 간격이 초과?
            {
                // 간격이 이하이면 false
                if(dist <= num)
                    return false;                
                break;
            }                
        }
    }
    
    return true;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    
    characters = "ACFJMNRT";
    ch = vector<bool>(8, false);
    sel = vector<int>(8, -1);
    answer = 0;
    cnt = 8;
    
    do {
        map<char, int> m;
        for(int i = 0; i < cnt; ++i)
            m[characters[i]] = i;
        
        if(checkValid(data, m))
            ++answer;
        
    } while(next_permutation(characters.begin(), characters.end()));
    
    return answer;
}

• DFS를 이용하여 직접 순열을 구하지 않고, 내장된 함수인 next_permutation 함수를 이용하여 더욱 간편하게 문제를 해결할 수 있습니다.
• 이 방법에서 do-while을 사용한 이유는, while문을 먼저 사용할경우, next_permutation을 먼저 호출하여 첫번째 순열부터 검사를 시작하기 때문입니다. 초기 값인 "ACFJMNRT"가 검사되지 않습니다.
• DFS를 이용하여 직접 구현하는 방식보다 성능이 좋습니다. 위 DFS를 활용한 방식은 4500ms가 나온 반면, 함수를 통해 구현한 방식은 4000ms로 약 10%의 성능 개선이 있습니다.