프로그래머스 Level 2 단체사진찍기

단체사진찍기 (프로그래머스 Level 2)

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

특정 조건을 만족하는 경우의 수를 따지는 문제다
8개의 수를 일렬로 세우는 데는 8! = 약 4만 에 해당하는 탐색을 해야하며
해당 순서에서 조건을 만족하는지 확인해야 하므로
백트래킹을 사용하여 최대한 탐색 횟수를 줄이는 쪽으로 방향을 잡았다

조건을 저장할 수 있도록 구조체를 사용하였고
조건에 해당하는 data에 바로 접근 가능하도록 unordered_map을 사용하였다

풀이 자체는 dfs + 백트래킹이기에 간단하나
옆에 세울때,

1. 조건이 있는지 확인
   
2. 조건이 있다면 조건에 맞는 녀석이 현재 배열에 서있는지 확인
   
3. 배열에 서 있다면, 거리 확인
   을 통해 조건에 맞지 않으면 그냥 pass 하고 다음 사람으로 넘어가는 방식을 사용하였다
   

문제 자체는 백트래킹과 재귀 풀이법을 알면 그렇게 어렵지는 않지만
역시 재귀 쪽 문제는 디버깅도 힘들다
(예상 값이 다른 경우, 원인을 찾기 힘들다)

Code

#include <string>
#include <vector>
#include<unordered_map>
#include<math.h>

using namespace std;

const int MaxCount = 8;
const char peoples[MaxCount] = { 'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T' };

struct condition
{
	char Target;
	int distance;
	bool isSame;
	bool isLess;
	bool isMore;
};

void dfs(unordered_map<char, int>& arr, unordered_map<char, vector<condition>>& conditions, int& answer, int nowCount)
{
	if (nowCount == MaxCount)
	{
		answer++;
		return;
	}

	for (char c : peoples)
	{
		// 이미 존재하는 단어
		if (arr.find(c) != arr.end())
			continue;

		// 별다른 조건 없는 수이다
		if (conditions.find(c) == conditions.end())
		{
			arr[c] = nowCount;
			dfs(arr, conditions, answer, nowCount + 1);
			arr.erase(c);
			continue;
		}

		// 나 자신의 조건 검사
		bool isNotCondition = true;
		for (auto& con : conditions[c])
		{
			char target = con.Target;

			// 지금 목표가 배열 내에 없네? 다른 조건 검사
			if (arr.find(target) == arr.end())
			{
				continue;
			}

			// 거리 검사
			int dis = abs(arr[target] - nowCount) - 1;

			if ((con.isLess && dis >= con.distance) ||
				(con.isMore && dis <= con.distance) ||
				(con.isSame && dis != con.distance))
			{
				isNotCondition = false;
				break;
			}
		}

		if (isNotCondition)
		{
			arr[c] = nowCount;
			dfs(arr, conditions, answer, nowCount + 1);
			arr.erase(c);
		}
	}
}

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

	unordered_map<char, vector<condition>> conditions;

	for (string str : data)
	{
		char start = str[0];
		char target = str[2];
		char cond = str[3];
		int dis = int(str[4] - '0');

		if (conditions.find(start) == conditions.end())
			conditions[start] = vector<condition>();

		conditions[start].push_back({ target,dis,false,false,false });

		if (conditions.find(target) == conditions.end())
			conditions[target] = vector<condition>();

		conditions[target].push_back({ start,dis,false,false,false });

		switch (cond)
		{
		case '=':
		{
			conditions[start].back().isSame = true;
			conditions[target].back().isSame = true;
		}
		break;
		case '<':
		{
			conditions[start].back().isLess = true;
			conditions[target].back().isLess = true;
		}
		break;
		case '>':
		{
			conditions[start].back().isMore = true;
			conditions[target].back().isMore = true;
		}
		break;
		}
	}

	unordered_map<char, int> arrays; // 일렬로 세운 (사람, 위치)
	dfs(arrays, conditions, answer, 0);

	return answer;
}