[프로그래머스 문제풀이] 22. 피로도

나의 풀이

저번에 풀었던 소수찾기 문제에서 약간 변형을 해서 문제를 해결했다.
던전들을 완전탐색해야 하기 때문에
던전이 3개일 때 매개변수로 "012"를 넣으면 도출되는 조합은 다음과 같다.

012
021
102
120
210
201

나온 결과에서 숫자 하나씩 던전 컨테이너의 인덱스로 접근하면
가능한 모든 순서를 반복하여 던전을 돈다.

---

🎉완성코드

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

using namespace std;

int STATIC_K = 0;
int g_k = 0;
vector<vector<int>> g_dungeons;

static int max_cnt = 0;

int play_dungeons(string orders)
{
	for (size_t i = 0; i < orders.size(); i++)
	{
		int now = orders[i] - '0';

		//cout << g_k <<' '<< i << ' '<< g_dungeons[now][0]<< ' '<< g_dungeons[now][1]<< endl;
		if (g_dungeons[now][0] <= g_k)
			g_k -= g_dungeons[now][1];
		else
		{
			return i;
		}
	}
	return orders.size();
}

void mix_func(string mix, int pos, string numbers)
{
	//사이즈까지 모든 조합
	//cout << "mix: " << mix << endl;

	//사이즈가 채워질 때 조합
	if (pos == mix.size())
	{
		g_k = STATIC_K;
		max_cnt = max(max_cnt, play_dungeons(mix));

		//cout << "mix: " << mix << endl;
		//cout << "max: " << max_cnt << endl;
		return;
	}

	for (size_t i = 0; i < numbers.size(); i++)
	{
		string a = numbers;
		string m = mix;
		int p = pos;
		m[p] = a[i];
		a.erase(a.begin() + i);

		mix_func(m, ++p, a);
	}
}

int solution(int k, vector<vector<int>> dungeons) {
	STATIC_K = k;
	g_k = k;
	g_dungeons = dungeons;

	string numbers;
	numbers.resize(dungeons.size());

	for (int i = 0; i < dungeons.size(); i++)
	{
		numbers[i] = i + '0';
	}

	string mix;
	mix.resize(numbers.size());

	mix_func(mix, 0, numbers);

	return 	max_cnt;
}

---

추천을 많이 받은 풀이

DFS 알고리즘 방식을 활용하여 문제를 해결했다.

void dfs(int h){
    if(answer < h)
        answer = h;

    cout << "h : " << h << endl;
    cout << visit[0] << visit[1]<< visit[2]<< endl;

    for(int i=0; i<N; i++){
        if (visit[i])
        {
            continue;
        }
        
        visit[i] = 1;
        //전역변수로 컨테이너에 visit대로 접근하기
        cout << To_Search[i] << endl;
        dfs(h+1);
        cout <<"상위노드로"<< endl;
        visit[i] = 0;
    }
}

나도 DFS 알고리즘을 활용하여 문제를 풀어보려 했지만 실패했다.
여기서 재귀호출 뒤에 코드를 작성하면 꼬리 노드의 작업이 끝날 때마다 실행된다는 것을 알게 되었다.

visit에 접근 가능한 위치를 담아 두는데
재귀호출 후 visit[i] = 0 으로 상위 노드로 올라가도록 구현되었다.

---

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

using namespace std;

int answer = 0;
vector<vector<int>> dungeons;
int N;

int visit[8];
void dfs(int h, int p){
    if(answer < h)
        answer = h;

    for(int i=0; i<N; i++){
        if(visit[i] || dungeons[i][0] > p)
            continue;

        visit[i] = 1;
        dfs(h+1, p-dungeons[i][1]);
        visit[i] = 0;
    }
}

int solution(int k, vector<vector<int>> dungeons_) {
    dungeons = dungeons_;
    N = dungeons.size();

    dfs(0, k);

    return answer;
}

피로도 문제 링크