글 읽기 - top - down DP 최종 state 정의하기

sc3289 2년 전 0

1102 발전소 문제나

2098 외판원 순회 문제를 풀 때

top down - dp로 푼 풀이들을 보면

최종 state가 시작점이 되더라구요?

발전소 문제는 처음에 켜져있는 발전소의 비트 마스크 ex) 001

외판원 순회 문제는 시작 마을을 1로 잡았을때 1만 켜져있는 비트마스크 ex) 000001

return 값이 어떻게 초기 상태가 되는지 잘 모르겠습니다... 이러면 중복 호출을 어떻게 막아주는건가요?

top-down 방식으로 DP를 푼다면 피보나치처럼

fibo 15를 구하라고 문제에서 주어지면

return fibo(14) + fibo(13); 이렇게 최종 state에 대한 값을 리턴하지 않나요?

직관적으로 봐도 중복호출되는 함수들 처리가 되구요.

아래 코드는 외판원 순회 문제를 최종 state를 11111로 잡고 시작한 제 코드입니다.

#include <stdio.h>
#define MIN(a , b) ( ((a) < (b)) ? (a) : (b) )

int impossible = 1000000000;

int n, arr[16][16], dp[16][1<<16];

int tsp(int,int);

int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            scanf("%d",&arr[i][j]);
    }
    printf("%d",tsp(0,(1<<n)-1));
    // 최종 state는 모든 마을을 방문한 상태
    return 0;
}


int tsp(int cur, int visit)
{
    if(dp[cur][visit]>0)
        return dp[cur][visit];
    if((visit & ~(1<<cur)) == 0) // base condition
    {
        if(arr[0][cur] == 0)
            return impossible;
        else
            return arr[0][cur];
    }
    dp[cur][visit] = impossible;
    for(int i=1;i<n;i++)
    {
        if( i!=cur && ((1<<i)&visit)!=0 && arr[i][cur] != 0)
            dp[cur][visit] = MIN(dp[cur][visit],tsp(i,visit&~(1<<cur))+arr[i][cur]);
    }
    return dp[cur][visit]; // final state
}

ckdgus2482 2년 전 1

재귀함수의 기능을 정의하기 나름이죠.

이미 방문한 점의 집합을 파라미터로 받아서 순회한다고 정의하고 구현할 수도 있고, 앞으로 방문해야 하는 점의 집합을 파라미터로 받아서 순회한다고 정의하고 구현할 수도 있잖아요.

어차피 결과적으로 주어진 전체 도시를 순회해야하는 문제니까 어떤 구현이든 어색하지 않습니다.

만약 전체가 아니라 일부를 선택해서 순회해야 한다면 방문해야할 점의 집합을 넘겨주는게 구현상 편리할 것 같네요.

sc3289 2년 전 0

상태를 정의하기 나름인데 Top - down DP는 최종상태에서 거슬러 내려가는 거라는 이미지가 어쩌다 박혀버렸는지... 한참 고민했네요...

감사합니다

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

top - down DP 최종 state 정의하기

sc3289 2년 전 0

ckdgus2482 2년 전 1

sc3289 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말