[PS] 백준 10265번: MT

|

문제

내가 이해한 문제 내용

$n$명의 사람들간의 의존관계 (너가 안가면 나도 안가)가 주어질 때 MT에 갈 수 있는 최대한의 사람 수를 구하시오.

접근 방식

  1. 유니온파인드 + DP로 접근했으나 실패
  2. 이후 SCC를 공부하고 시도해보았으나 어려워서 실패
  3. 해답을 보니 DFS + DP (풀이)

먼저 $n$명의 사람을 1번째부터 $n$번째라고 하면 $n$번째 사람부터 차에 태우는 경우와 태우지 않는 경우에 대해 계산을 한다. 그러니까 top-down 방식의 재귀인셈. 해당 사람에 대해서 계산을 한 결과를 캐싱하고 캐싱한 부분을 그 이전 사람, 여기선 $n-1$번째 사람을 태우는 경우와 태우지 않는 경우에 이용한다.

$n-1$번째 사람을 태운다면 다시 $n$번째 사람을 태우는 경우와 태우지 않는 경우를 봐야 하는데 이 때 DFS를 이미 $n-1$번째에 시도했으므로 $n$번째 사람의 경우는 고려하지 않는다. 만약 $n-1$번째 사람을 태우지 않는다면 이전에 캐싱했던 $n$번째 사람을 태우는 경우와 태우지 않는 경우 중 최댓값으로 할당해주면 된다.

어려웠던 점 & 배운 점

  • DFS를 이렇게 쓰니까 너무 어려웠음
  • DFS+Knapsack 풀이가 공식풀이인데 이해가 안됨
  • SCC를 사용하는 방식도 이해가 안됨.

시간복잡도

$O(n^2)$인 것 같긴 한데… 그래프가 연결그래프라면 연결요소가 1개이고 끝까지 들어가서 top-down으로 돌리니까 $1+2+…+n$이어서 뭔가 맞는것 같지만 불확실.

코드

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

int a[1001];
int n,k,c,u;
int visited[1001];
int dp[1001][1001];

int dfs(int v, int num)
{
    visited[v] = 1;
    if(!visited[a[v]]) 
        num = dfs(a[v],num+1);
    return num;
}

void cleanVisit(int index)
{
    visited[index] = 0;
    if(visited[a[index]]) {
        cleanVisit(a[index]);
    }
}

int ride(int index, int current)
{
    int &ret = dp[index][current];
    if(ret!=-1) return ret;
    if(index>n) return 0;

    // 묶음을 계산하지 않음 + 태우지 않음
    ret = ride(index+1,current);

    if(!visited[index]) {
        // 묶음을 계산함, 즉 DFS로 방문하게 됨
        int needs = dfs(index,1);
        if(current+needs<=k) {
            // 태우지 않음, 태움
            ret = max(ride(index+1,current+needs)+needs,ride(index+1,current));
        }
        cleanVisit(index);
    }
    return ret;
}

int main(void)
{
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++){
        scanf("%d",&u);
        a[i] = u;
    }

    memset(dp,-1,sizeof(dp));
    printf("%d",ride(1,0));

    return 0;
}