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

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

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

알고리즘 키워드

- 문자열 조작

- DFS

 

전역 변수를 안 써야 통과할 수 있는 문제다..

안내에서는 전역 변수를 초기화해서 쓰라했지만, 초기화를 해도 통과가 안된다ㅠㅠ

그래서 걍 안 써버리고 call by reference 스타일로 문제를 풀었다.

DFS 식으로 한 명 배치할 때마다 이전에 배치된 애들과 주어진 조건에 위배되는지를 확인하면서 DFS로 탐색을 하고, 수를 세면 된다.

 

#include <string>
#include <vector>
#include <iostream>
using namespace std;
struct Condition {
    string a, b, symbol;
    int dist;
};

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
void dfs(int idx, vector<Condition> &conditions, vector<bool> &visited, int &answer, vector<string> &kakao, string &line);
bool check(string new_friend, int idx, vector<Condition> &conditions, string &line);
int solution(int n, vector<string> data) {
    int answer = 0;
    string line = "";
    vector<bool> visited(8, false);
    vector<Condition> conditions;
    vector<string> kakao;
    for(int i = 0;i < n;i++) {
        string a = data[i].substr(0, 1);
        string b = data[i].substr(2, 1);
        string symbol = data[i].substr(3, 1);
        string dist = data[i].substr(4, 1);
        
        conditions.push_back(Condition({a, b, symbol, stoi(dist)}));
    }
    kakao = {"M", "C", "F", "J", "A", "N", "R", "T"};
    
    
    dfs(0, conditions, visited, answer, kakao, line);
    return answer;
}

void dfs(int idx, vector<Condition> &conditions, vector<bool> &visited, int &answer, vector<string> &kakao, string &line) {
    if(idx == 8) {
        answer++;
        return;
    }
    
    for(int i = 0;i < 8;i++) {
        if(visited[i] == false && check(kakao[i], idx, conditions, line)) {
            line += kakao[i];
            visited[i] = true;
            dfs(idx + 1, conditions, visited, answer, kakao, line);
            visited[i] = false;
            line = line.substr(0, line.length() - 1);
        }
    }
}

bool check(string new_friend, int idx, vector<Condition> &conditions, string &line) {
    for(int i = 0;i < line.length();i++) {
        string cmp_friend = "";
        cmp_friend += line[i];
        int dist1 = line.length() - i - 1;
        for(int j = 0;j < conditions.size();j++) {
            if((new_friend == conditions[j].a && cmp_friend == conditions[j].b) ||
               (cmp_friend== conditions[j].a && new_friend == conditions[j].b)) {
                string symbol = conditions[j].symbol;
                int dist2 = conditions[j].dist;
                
                if(symbol == "=") {
                    if(dist1 != dist2) {
                        return false;
                    }
                }
                else if(symbol == ">") {
                    if(dist1 <= dist2) {
                        return false;
                    }
                }
                else if(symbol == "<") {
                    if(dist1 >= dist2) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}