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

https://programmers.co.kr/learn/courses/30/lessons/1835

코딩테스트 연습 - 단체사진 찍기

---

 문제 풀이

백트래킹을 통해서 구현하였다.

거리는 따지는 것이 중요하다. 인덱스를 통해서 둘 사이의 거리를 따지기 때문에

주어진 조건의 거리에서 +1 된 값으로 비교해야 한다.

 느낀 점

C++에서 제공하는 "next_permutation" 함수로 해결해도 되는 문제이지만 백트래킹으로 구현하고 싶어서 구현했다. 사실 그렇게 크게 어렵지 않은 문제인데 백트래킹이 오랜만이라서 버벅거렸다.

 코드

#include <string>
#include <vector>

using namespace std;

int answer;
bool visited[8];
string friends = "ACFJMNRT";
vector<char> v;

void DFS(int cnt, vector<char> v, vector<string> data) {
    if (cnt == 8) {
        for (int i = 0; i < data.size();i++) {
            char n1 = data[i][0]; 
            char n2 = data[i][2];
            char op = data[i][3];
            int dist = data[i][4] - '0';
            dist++;

            int idx1, idx2;
            idx1 = idx2 = -1;
            for (int j = 0; j < 8; j++) {
                if (v[j] == n1) idx1 = j;
                if (v[j] == n2) idx2 = j;
            }
            if (op == '=' && abs(idx1 - idx2) != dist) return;
            if (op == '>' && abs(idx1 - idx2) <= dist) return;
            if (op == '<' && abs(idx1 - idx2) >= dist) return;
        }
        answer++;
        return;
    }
    for (int i = 0; i < 8;i++) {
        if (visited[i]) continue;
        visited[i] = true;
        v.push_back(friends[i]);
        DFS(cnt+1, v, data);
        visited[i] = false;
        v.pop_back();
    }
}

int solution(int n, vector<string> data) {
    answer = 0;
    DFS(0, v, data);
    return answer;
}