[프로그래머스/C] 피로도

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

프로그래머스

 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int visited[8];
int max_cnt;

void dfs(int k, int **dungeons, size_t dungeons_rows, int n) {
    if (n > max_cnt)
        max_cnt = n;
    
    for (int i = 0; i < dungeons_rows; i++) {
        if (!visited[i] && dungeons[i][0] <= k) {
            visited[i] = 1;
            dfs(k - dungeons[i][1], dungeons, dungeons_rows, n + 1);
            visited[i] = 0;
        }
    }
}

int solution(int k, int** dungeons, size_t dungeons_rows, size_t dungeons_cols) {
    dfs(k, dungeons, dungeons_rows, 0);
    return max_cnt;
}

 

 

• 전역 변수:
  • visited: 던전의 방문 여부를 기록한다.
  • max_cnt: 탐험한 던전의 최대 개수를 저장한다.
• DFS 함수:
  • k: 현재 남은 피로도
  • dungeons: 던전 정보가 담긴 2차원 배열
  • dungeons_rows: 던전 배열의 행 길이
  • n: 현재 탐험한 던전의 개수.
  • 현재 탐험한 던전의 수가 max_cnt보다 크면 max_cnt를 갱신한다.
  • 각 던전을 순회하며 방문하지 않았고, 최소 필요 피로도를 만족하면 탐험. 탐험 후에는 원상복구하여 다른 경로를 탐색.
• Solution 함수:
  • 주어진 피로도 k와 던전 정보를 바탕으로 최대 탐험 던전 수를 계산
  • DFS 함수를 호출하여 탐색을 시작하고, 최종적으로 최대 탐험 던전 수를 반환