[C] 프로그래머스 '피로도' 풀이

TL;DR

프로그래머스 피로도 문제는 던전 순서를 전부 바꿔 보며 최대로 방문한 개수를 찾는 백트래킹 문제다.

처음에는 종료 조건을 M == 0으로 잡아서 막혔고, 그다음에는 재귀 함수 이름을 잘못 불러서 또 틀렸다.

이 글은 C에서 solution()과 실제 재귀 함수 sol()을 섞어 부르면 왜 답이 깨지는지를 기록한다.

배경

피로도 문제의 입력은 현재 피로도 k와 던전 배열 dungeons다.

각 던전은 [최소 필요 피로도, 소모 피로도] 형태다.

목표는 단순하다.

현재 피로도로 입장 가능한 던전을 고르고, 방문 처리한 뒤, 남은 던전 중 다시 갈 곳을 고른다.

모든 순서를 탐색하면서 가장 많이 방문한 횟수를 저장한다.

처음엔 M을 남은 던전 수처럼 생각했다.

그래서 던전을 하나 돌 때마다 M - 1을 넘기고, M == 0이 되면 답을 올리는 식으로 접근했다.

int answer = -1;
int vis[9];

int sol(int k, int** dungeons, size_t dungeons_rows, int M) {
    if(M==0){answer++; return answer;}
    for(int i=0;i<dungeons_rows;i++){
        if(!vis[i]){
            if(k<dungeons[i][0]){ continue; }
            vis[i]=1;
            k-=dungeons[i][1];
            solution(k,dungeons,dungeons_rows,M-1);
            vis[i]=0;
        }
    }
}

이 코드는 모든 던전을 다 도는 경우만 답으로 본다.

하지만 피로도 문제는 중간에 더 이상 갈 던전이 없어도 그때까지 방문한 개수를 답 후보로 봐야 한다.

삽질 과정

종료 조건을 고친 뒤에는 M을 지금까지 방문한 던전 수로 바꿨다.

매 호출마다 answer를 갱신하면, 더 들어갈 수 없는 지점에서도 현재 기록이 남는다.

int answer=0;
int vis[9]={0,};

int sol(int k, int** dungeons, size_t dungeons_rows, int M) {
    if(M>answer) answer=M;
    for(int i=0;i<dungeons_rows;i++){
        if(!vis[i]&& k>=dungeons[i][0]){
            vis[i]=1;
            solution(k-dungeons[i][1],dungeons,dungeons_rows,M+1);
            vis[i]=0;
        }
    }
}

겉보기에는 거의 맞다.

vis[i]로 방문 표시를 남기고, 재귀 호출 후 다시 0으로 복구한다.

k - dungeons[i][1]도 인자로 넘겨서 이전 피로도 상태가 현재 스택에 남는다.

그런데 한 줄이 문제였다.

solution(k-dungeons[i][1],dungeons,dungeons_rows,M+1);

여기서 부른 함수는 재귀 함수 sol()이 아니라 프로그래머스 제출용 입구 함수 solution()이다.

solution()은 매번 answer=0으로 초기화하고, 다시 sol()을 처음부터 호출한다.

재귀로 깊게 들어간다고 생각했지만, 실제로는 시작점으로 계속 되돌아간 셈이다.

해결 코드

재귀 호출 대상만 sol()로 바꾸면 된다.

전역 변수는 프로그래머스가 여러 테스트 케이스를 돌릴 때 값이 남지 않도록 solution()에서 초기화한다.

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

int answer = 0;
int vis[9] = {0,};

int sol(int k, int** dungeons, size_t dungeons_rows, int M) {
    if (M > answer) answer = M;

    for (int i = 0; i < dungeons_rows; i++) {
        if (!vis[i] && k >= dungeons[i][0]) {
            vis[i] = 1;
            sol(k - dungeons[i][1], dungeons, dungeons_rows, M + 1);
            vis[i] = 0;
        }
    }

    return 0;
}

int solution(int k, int** dungeons, size_t dungeons_rows, size_t dungeons_cols) {
    answer = 0;

    for (int i = 0; i < 9; i++) {
        vis[i] = 0;
    }

    sol(k, dungeons, dungeons_rows, 0);

    return answer;
}

M은 현재까지 방문한 던전 수다.

answer는 탐색 도중 만난 최대 M이다.

갈 수 있는 던전만 고르므로 k >= dungeons[i][0]가 가지치기 조건이 된다.

백트래킹에서 봐야 할 지점

백트래킹은 상태를 선택하고, 더 깊게 들어갔다가, 원래 상태로 되돌리는 흐름이다.

이 문제에서는 방문 배열만 직접 복구하면 된다.

vis[i] = 1;
sol(k - dungeons[i][1], dungeons, dungeons_rows, M + 1);
vis[i] = 0;

k는 함수 인자로 계산해서 넘겼기 때문에 별도 복구가 필요 없다.

반대로 k -= dungeons[i][1]처럼 현재 변수 값을 직접 바꾸면 재귀가 끝난 뒤 k += dungeons[i][1]로 되돌려야 한다.

작은 차이지만, C로 백트래킹을 짤 때 이 부분에서 자주 꼬인다.

배운 것

재귀 함수와 제출용 함수는 역할을 나눠야 한다.

프로그래머스의 solution()은 입구 함수로 두고, 실제 탐색은 별도 함수가 맡는 편이 안전하다.

다음에 백트래킹이 막히면 상태 선택 → 재귀 호출 → 상태 복구 세 줄부터 확인한다.