서론
오늘은 프로그래머스의 "피로도" 문제를 풀어보았습니다. 이 문제는 게임 내 피로도 시스템을 바탕으로 최대한 많은 던전을 탐험하는 방법을 찾는 것이 목표입니다.
문제 분석
문제의 핵심은 다음과 같습니다:
•
각 던전마다 "최소 필요 피로도"와 "소모 피로도"가 주어집니다.
•
현재 피로도 k와 던전 정보가 주어질 때, 탐험 가능한 최대 던전 수를 구해야 합니다.
•
던전의 개수는 최대 8개로 제한되어 있습니다.
이 문제의 핵심은 던전 탐험 순서에 따라 결과가 달라질 수 있다는 점입니다. 따라서 모든 가능한 경우를 고려해야 합니다.
계획 수립
처음에는 최소 피로도 순으로 정렬하여 접근하려 했지만, 이는 최적의 해를 보장하지 않습니다. 던전의 개수가 8개 이하로 제한되어 있기 때문에, 모든 경우의 수를 고려하는 완전 탐색(브루트 포스) 방식으로 접근하기로 결정했습니다.
알고리즘으로는 깊이 우선 탐색(DFS)을 선택했습니다. 이는 모든 가능한 던전 탐험 순서를 효과적으로 탐색할 수 있기 때문입니다.
코드 작성
다음은 문제 해결을 위한 코드의 주요 구조입니다:
#include <string>
#include <vector>
#include <iostream>
using namespace std;
int dfs(vector<vector<int>> dungeons, int n, int k, int cnt)
{
if (n==dungeons.size())
return cnt;
else
{
int result1 = 0;
int result2 = 0;
cout << n << "," << k << "," << cnt << endl;
if (k >= dungeons[n][0]) {
result1 = dfs(dungeons, n+1, k-dungeons[n][1], cnt+1);
}
result2 = dfs(dungeons, n+1, k, cnt);
if (result1>result2)
return result1;
else
return result2;
}
}
int solution(int k, vector<vector<int>> dungeons)
{
int answer = -1;
answer = dfs(dungeons, 0, k, 0);
return answer;
}
C++
복사
이 코드에서 핵심은 DFS 함수입니다. 이 함수는 현재 던전 인덱스, 남은 피로도, 탐험한 던전 수를 매개변수로 받아 재귀적으로 모든 경우를 탐색합니다.
문제 해결 및 보완
코드 작성 과정에서 몇 가지 문제점을 발견하고 수정했습니다:
1.
처음에는 방문 여부를 체크하는 배열을 사용했지만, 이는 불필요한 복잡성을 추가했습니다.
2.
최소 피로도 순으로 정렬하는 것이 항상 최적해를 주지 않는다는 것을 깨달았습니다.
이러한 문제점들을 해결하기 위해 코드를 다음과 같이 수정했습니다:
#include <string>
#include <vector>
using namespace std;
int dfs(vector<vector<int>> dungeons, vector<bool> visit, int k)
{
vector<int> results;
for (int i=0; i<visit.size(); i++)
{
if (!visit[i] && (k>=dungeons[i][0]))
{
visit[i] = true;
results.push_back(dfs(dungeons, visit, k-dungeons[i][1]));
visit[i] = false;
}
}
int max = 0;
for (int n : results)
{
if (n>max)
max = n;
}
if (max==0)
{
for (bool v: visit)
if (v)
max += 1;
}
return max;
}
int solution(int k, vector<vector<int>> dungeons)
{
int answer = -1;
vector<bool> visit(dungeons.size(), false);
answer = dfs(dungeons, visit, k);
return answer;
}
C++
복사
이 수정된 버전에서는 각 던전을 탐험하는 경우와 탐험하지 않는 경우를 모두 고려하여 최적의 결과를 찾습니다.
회고
이번 문제를 통해 깊이 우선 탐색(DFS)의 활용법을 다시 한 번 복습할 수 있었습니다. 처음에는 문제를 단순화하려고 했지만, 때로는 모든 경우를 고려하는 것이 더 정확한 해법을 제공한다는 것을 깨달았습니다.
앞으로의 개선점으로는, 문제 해결 접근 방식을 더 유연하게 가져갈 필요가 있다고 생각합니다. 초기에 최적화를 고려하기보다는, 먼저 정확한 해법을 찾고 그 다음 최적화를 고려하는 것이 더 효과적일 것 같습니다.
