[99클럽/코딩테스트 챌린지/C++] 완전 탐색과 원복 (피로도 문제)

문제 링크 : 

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

프로그래머스

문제 요약

이 문제는 주어진 현재 피로도 kkk와 여러 던전의 "최소 필요 피로도"와 "소모 피로도"를 활용해, 최대 몇 개의 던전을 탐험할 수 있는지를 계산하는 문제입니다. 던전을 탐험하기 위해서는 다음 조건을 만족해야 합니다:

1. 현재 남은 피로도가 "최소 필요 피로도" 이상이어야 탐험이 가능합니다.
2. 탐험한 던전 수를 최대화해야 합니다.

문제를 해결하기 위해 모든 가능한 탐험 경로를 탐색하고, 상태를 복구(원복)하며 탐색을 진행해야 합니다.

접근법

완전 탐색

1, 모든 가능한 던전 탐험 순서를 탐색해야 하므로, 완전 탐색(Brute Force) 방식으로 문제를 해결합니다.

2, 각 던전마다 현재 남은 피로도가 탐험 가능하다면:

• 해당 던전을 탐험하고 다음 단계로 이동합니다.
• 탐색이 끝난 후 상태를 복구(원복)하여 다른 경로를 탐험합니다.

3, 이를 통해 최적의 탐험 수를 계산할 수 있습니다.

원복의 중요성

1, 탐험 과정에서 상태를 변경한 후, 다른 경로를 탐색하기 위해 이전 상태로 복구하는 작업을 원복(Backtracking)이라고 합니다.

2, 원복이 없으면, 탐색이 중첩되거나 중복 방문이 발생해 잘못된 결과를 초래할 수 있습니다.

3, 이 문제에서는:

1. 남은 피로도 (remain)
2. 탐험한 던전 수 (counts)
3. 방문 여부 (visited)

이 세 가지 상태를 원복해야 정확한 결과를 얻을 수 있습니다.

 

코드

#include <string>
#include <vector>

using namespace std;

int remain = 80; // 현재 남은 피로도
int counts = 0;  // 탐험한 던전 수
int answer = -1; // 탐험 가능한 최대 던전 수
vector<int> visited; // 방문 여부 추적

// 모든 던전을 탐색하는 함수
void findDungeon(vector<vector<int>>& dungeons) {
    for (int i = 0; i < dungeons.size(); i++) {
        // 최소 필요 피로도를 만족하지 못하거나 이미 방문한 던전은 스킵
        if (dungeons[i][0] > remain) continue;
        if (visited[i]) continue;

        // 상태 변경: 던전 탐험
        remain -= dungeons[i][1]; // 피로도 소모
        counts++; // 탐험한 던전 수 증가
        visited[i]++; // 던전 방문 처리

        // 최대 탐험 던전 수 갱신
        answer = max(answer, counts);

        // 다음 단계 탐색
        findDungeon(dungeons);

        // 원복(Backtracking): 상태 복구
        remain += dungeons[i][1]; // 소모된 피로도 복구
        visited[i]--; // 방문 상태 초기화
        counts--; // 탐험 던전 수 감소
    }
}

int solution(int k, vector<vector<int>> dungeons) {
    remain = k; // 초기 피로도 설정
    answer = -1; // 최대 탐험 던전 수 초기화

	for(int i = 0; i < dungeons.size(); i++)
	{
		// 현재 i 번쨰 던전의 필요 피로도가 현재 플레이어의 피로도 보다 크다면
		// 다음 던전으로 이동
        if (dungeons[i][0] > k) continue; // 탐험 불가능한 던전 스킵

        visited = vector<int>(dungeons.size()); // 방문 여부 초기화
        remain = k; // 남은 피로도 초기화
        counts = 0; // 탐험 던전 수 초기화

        findDungeon(dungeons); // 탐색 시작
	}

    return answer;
}

문제 해결 과정

1. 완전 탐색 구현

• 모든 던전을 탐험할 수 있도록 반복문과 재귀를 사용해 경로를 탐색합니다.
• 각 단계에서 탐험 가능한 던전인지 확인하고, 가능하다면 탐험 후 다음 단계로 이동합니다.

2. 상태 원복 구현

• 탐험 후 다른 경로를 탐색하기 위해 상태를 복구해야 합니다.
• 원복 작업:
  • 탐험 중 소모된 remain(피로도)을 복구합니다.
  • 탐험 던전 수 counts를 감소시킵니다.
  • 방문 여부 visited를 초기 상태로 복구합니다.

3. 최대값 갱신

• 탐험 경로를 진행할 때마다 answer 값을 갱신합니다.
• 탐색이 종료되면 최적의 결과가 answer에 저장됩니다.

배운 점

1, 완전 탐색과 원복의 역할

• 완전 탐색은 모든 경로를 탐색하며 최적의 결과를 도출하기 위해 필수적입니다.
• 탐색 과정에서의 상태 원복(Backtracking)은 탐색 경로를 올바르게 유지하는 핵심 요소입니다.

2, 재귀 함수 내 상태 관리

• 재귀 호출은 현재 상태를 변경하므로, 호출 후에는 반드시 상태를 복구해야 합니다.
• 원복을 통해 다른 경로 탐색에 영향을 주지 않도록 하는 것이 중요합니다.

3, 방문 여부와 조건 처리

• 방문 여부(visited)를 효율적으로 관리하지 않으면, 중복 방문이나 잘못된 경로 탐색이 발생할 수 있습니다.
• 각 던전의 조건을 정확히 체크하고, 조건에 맞지 않는 경우 탐색을 건너뛰는 것이 필요합니다.

결론

이 문제를 통해 완전 탐색과 Backtracking(원복)의 중요성을 다시금 깨달을 수 있었습니다. 완전 탐색은 모든 경로를 탐색하며 최적의 결과를 보장하고, Backtracking은 각 경로를 독립적으로 관리하여 정확한 계산을 가능하게 합니다.

앞으로도 복잡한 탐색 문제를 해결할 때, 원복과 상태 관리를 철저히 하여 최적의 결과를 얻도록 하겠습니다.