백준 1005번 문제. ACM Craft

백준 1005번 문제. ACM Craft

[Point] DP와 DFS를 짬뽕시켜 풀어보자.

개인적으로 좀 고난에 빠졌던 문제.

분명 알고리즘 분류에 "위상정렬"이라고 들어가있는데, 나는 위상정렬로 어떻게 풀어야할지 떠오르지 않아서 다이나믹 프로그래밍과 DFS를 짬뽕시켰다.

찾아보니 이 분의 글이 "위상정렬" 관점에서 제일 설명이 잘 된 글 같다. (링크)

일단 목표건물 w부터 차례대로 역추적 DFS를 하려고 했다

DP배열은 0으로 초기화되어있으니 visit 배열의 역할을 대체하여 사용하였다. 

부분해의 후보들 중 가장 큰 값을 가진 후보가 부분해로 채택이 되고, 이런 부분해들이 모여 최종 해를 구할 수 있다 

(건물을 시공하려면 선행건물이 전부 다 건설되어야하기때문에 가장 건설시간이 긴 선행건물을 생각해야한다)

더이상 이동가능한 인접 노드가 없을 경우엔 (그래프의 시작점(들)) 그 자신의 건설시간=DP[시작점n] 이기 때문에 그다음 부분해가 구해지고..구해지고..또 구해져서 최종해가 구해지는 형태.

한가지 의문점은 adjMat 2차원배열을 지역변수로 넣었을땐 프로그램 에러가 났는데 전역으로 빼니 에러가 안난다는 점이다.

전역변수/지역변수의 차이점이 단지 영향력 범위에만 있는게 아니라 할당가능 사이즈에도 있는 것일까?

-> 친절한 분의 덧글로 의문점을 해결했다. 전역변수는 스택 메모리, 지역변수는 힙 메모리에 저장되는데 VS의 경우 기본 설정상 힙 메모리 할당 크기가 작아 이와 같은 문제가 생긴다고 한다. 백준 알고리즘 사이트는 VS로 돌아가는 것이 아니기 때문에, 다시 코드를 수정해 지역변수로 넣어도 통과함을 확인하였다. VS에서도 지역변수를 이용하고 싶다면 기본 설정을 만져주면 된다(프로젝트-[파일명]속성-좌측메뉴 링커-시스템-'힙 예약 크기' 수정) 보통 메모리 제한이 256MB이니 1024*1024*256 = 268435456 으로.

#include <stdio.h>
 
int adjMat[1001][1001]={0};
 
int DFS(int target,int N, int time[],int DP[]){
    int max=0,result=0;
    int i,answer;
 
 
    if(DP[target]!=0){
        return DP[target];
    }
 
    for(i=1;i<=N;i++){
        if(adjMat[i][target]==1){
            result=DFS(i,N,time,DP);
            if(max<result){
                max=result;
            }
        }
    }
 
    answer=time[target]+max;
    if(DP[target]<answer){
        DP[target]=answer;
    }
    return answer; 
}
 
int main(){
 
    
    int T,N,K,i,j,x,y,w;
    int time[1001]={0};
    int DP[1001]={0};
    
    scanf("%d",&T);
    
    for(i=0;i<T;i++){
        scanf("%d%d",&N,&K);
        
        for(j=0;j<=N;j++){ //DP 초기화
            DP[j]=0;
        }
 
        for(j=0;j<=N;j++){
            for(x=0;x<=N;x++){
                adjMat[j][x]=0;
            }
        }
        
 
        for(j=1;j<=N;j++){
            scanf("%d",&time[j]);
        }
 
        for(j=0;j<K;j++){
            scanf("%d%d",&x,&y);
            adjMat[x][y]=1;
        }
 
        scanf("%d",&w);
 
        printf("%d\n",DFS(w,N,time,DP));
        
    }
 
 
 
    return 0;
}