[PCCP] Lv2: 피로도(87946) 해설

문제

- 문제 링크: 피로도

 

코드

(C언어)

solution 1)

#include<>

solution 2)

#include<>

 

(C++)

solution 1)

- N: 던전의 개수

- 최악의 경우 모든 경로를 탐색하므로 경우의 수는 N*(N-1)*...*1이므로 시간복잡도는 O(N!)

#include <string>
#include <vector>

using namespace std;

int maxDepth = 0;
bool visited[8] = {false,};

// 던전의 최대 방문수를 갱신하면서 깊이 우선 탐색으로 던전 탐색
void exploreDungeon(int depth, int power, vector<vector<int>> &dungeons) {
    if (maxDepth < depth)
        maxDepth = depth;
        
    for (int i = 0; i < dungeons.size(); ++i) {
        // 이미 방문한 던전이거나, 최소 필요 피로도가 현재 남은 피로도보다 많을 때
        if (visited[i] || dungeons[i][0] > power)
            continue;
        
        // 방문이 가능한 모든 경우 확인
        visited[i] = true;
        exploreDungeon(depth + 1, power - dungeons[i][1], dungeons);
        visited[i] = false;
    }
}

int solution(int initialPower, vector<vector<int>> dungeons) {
    // 던전 탐색 시작
    exploreDungeon(0, initialPower, dungeons);
    
    return maxDepth;
}

solution 2)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

 

(Java)

solution 1)

- N: 던전의 개수

- 최악의 경우 모든 경로를 탐색하므로 경우의 수는 N!

- 최종 시간 복잡도: O(N!)

class Solution {
    private static int answer;
    private static int[][] Dungeons;
    private static boolean[] visited;
    
    // 백트래킹을 위한 DFS
    private static void backtrack(int k, int cnt) {
        for (int i = 0; i < Dungeons.length; ++i) {
            // 현재 피로도(k)가 i번째 던전의 최소 필요 피로도보다 크거나 같고, i번째 던전을 방문한 적이 없다면
            if (!visited[i] && k >= Dungeons[i][0]) {
                visited[i] = true; // i번째 던전을 방문 처리
                // 현재까지의 최대 탐험 가능 던전 수와 i번째 던전에서 이동할 수 있는 최대 탐험 가능 던전 수 중 큰 값을 선택하여 업데이트
                backtrack(k - Dungeons[i][1], cnt + 1);
                answer = Math.max(answer, cnt + 1);
                visited[i] = false; // i번째 던전을 다시 방문 취소
            }
        }
    }
    
    public int solution(int k, int[][] dungeons) {
        answer = 0;
        Dungeons = dungeons;
        // 던전 방문 여부를 저장할 배열
        visited = new boolean[dungeons.length];
        
        backtrack(k, 0); // DFS 메서드 수행
    
    	return answer;
    }
}

solution 2)

#include<>

 

(Python)

solution 1)

- N: 던전의 개수

- 최악의 경우 모든 경로를 탐색: O(N!)

# 백트래킹을 위한 DFS
def dfs(cur_k, cnt, dungeons, visited):
    answer_max = cnt
    for i in range(len(dungeons)):
        # 현재 피로도(cur_k)가 i번째 던전의 최소 필요 피로도보다 크거나 같고, i번째 던전을 방문한 적이 없다면
        if cur_k >= dungeons[i][0] and visited[i] == 0:
            visited[i] = 1 # i번째 던전을 방문 처리
            # 현재까지의 최대 참험 가능 던전 수와 i번째 던전에서 이동할 수 있는 최대 탐험 가능 던전 수 중 큰 값을 선택하여 업데이트
            answer_max = max(
                answer_max, dfs(cur_k - dungeons[i][1], cnt + 1, dungeons, visited)
            )
            visited[i] = 0
    return answer_max
        
# 최대 탐험 가능 던전 수를 계산하는 함수
def solution(k, dungeons):
    visited = [0] * len(dungeons)  # 던전 방문 여부를 저장할 지역 배열
    answer_max = dfs(k, 0, dungeons, visited)  # DFS 함수 호출
    return answer_max

solution 2)

import

 

(JavaScript)

solution 1)

- N: 던전의 개수

- 최악의 경우 모든 경로를 탐색: O(N!)

// 백트래킹을 위한 DFS
function dfs(curK, cnt, dungeons, visited) {
    let answerMax = cnt;
    for (let i = 0; i < dungeons.length; ++i) {
        // 현재 피로도(curK)가 i번째 던전의 최소 필요 피로도보다 크거나 같고, i번째 던전을 방문한 적이 없다면
        if (curK >= dungeons[i][0] && visited[i] === 0) {
            visited[i] = 1;
            // 현재까지의 최대 탐험 가능 던전 수와 i번째 던전에서 이동할 수 있는 최대 탐험 가능 던전 수 중 큰 값을 선택하여 업데이트
            answerMax = Math.max(answerMax, dfs(curK - dungeons[i][1], cnt + 1, dungeons, visited));
            visited[i] = 0;
        }
    }
    
    return answerMax;
}

// 최대 탐험 간으 던전 수를 계산하는 함수
function solution(k, dungeons) {
    const visited = Array(dungeons.length).fill(0); // 방문 여부를 저장할 지젹 배열
    const answerMax = dfs(k, 0, dungeons, visited); // DFS 함수 호출
    return answerMax;
}

solution 2)

import