백준 - 1005 ACM Craft

문제 링크

나는 BFS로 푼 문제이다. 시작 점이 꼭 1번 건물이 아닐 수도 있으므로 모든 건물의 정보를 입력 받는 과정에, 그 이전 단계가 있는 건물들은 시작 건물이 아니라 단정하고 시작 건물들이 가능한 건물들은 처음에 큐에 미리 넣어주고 BFS를 진행하였다.

이 문제에 함정이 있는 게, 문제는 최소 시간을 구하라고 하는데 따지고 보면 그냥 그 단계까지 누적 최고 건설 시간들만 구해주면 된다. 왜냐하면 특정 단계 건물을 짓기 위해서는 선행 건물들을 모두 지어야 하는데, 선행 건물들 중에 건설 시간이 짧은 것을 아무리 먼저 지어도 건설 시간이 긴 건물이 지어지기 전까지는 그 특정 단계의 건물을 지을 수 없기 때문이다. 

이 로직 대로 코드를 짰는데, 처음에 문제를 풀 때 시간 초과가 났었다. 뭐가 문제인가 고민을 해봤더니, 초기에는 build배열에서 첫 번째 인덱스는 현재 건물, 두 번째 인덱스는 다른 건물을 인덱스로 두고, 그 배열 값이 참이면 경로가 존재한다고 하고 풀이를 진행했었다.

이 과정에서 매 루프마다 그때의 건물 배열을 1부터, n까지 전부 다 경로 검사를 진행해야 하니 시간 초과가 일어난 것이다. 그래서 일일이 해당 인덱스에 저장하는 방법을 버리고 해당 건물이 가진 경로의 개수를 path 배열 에다가 저장하고, 배열의 1 인덱스부터 다음 경로들을 저장하는 방법을 택하니 시간 초과에서 벗어났다. 

밑은 위의 과정대로 작성한 코드이다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm> 
using namespace std;
//각 건물의 인덱스 0번에 건설 시간을 저장한다. 
int t,build[1001][1001],isFirst[1001]={0,},value[1001],path[1001];
int x,y,n,k,w;
queue<int> q; 
 
int bfs(){  
    int ret = 0;
    //시작점이 가능한 것들을 전부 큐에 넣는다. 
    for(int i=1;i<=n;i++){
        if(isFirst[i]==0){
            q.push(i);
            //초기 빌드의 누적 비용을 건설 비용으로 초기화한다. 
            value[i] = build[i][0];
        }
    }   
    //BFS를 진행한다. 
    while(!q.empty()){
        //큐에서 인덱스를 하나씩 꺼내서, 다음 경로에서 가능한 것을 찾는다.
         int p = q.front(); q.pop();
        //원하는 건물에 도달하면, 최대 값을 넣어준다.
         if(p==w) ret = max(ret,value[p]);
         else{
         for(int i=1;i<=path[p];i++){
            if(build[p][i]>=1){
                int a = build[p][i];
                // 다음 빌드를 짓는 데에 드는 최대 비용을 구한다. 최대 비용이 안되면 enqueue 하지 않는다.  
                if(value[a] < value[p]+build[a][0]){
                    value[a] =value[p] + build[a][0];
                    q.push(a);
                 }
             }
         }
        }
    }
    return ret;
}
int main(){
    scanf("%d",&t);
    while(t--){
        //초기화// 
        for(int i=0; i<q.size();i++) q.pop();
        memset(build,0,sizeof(build));
        memset(value,0,sizeof(value));
        memset(isFirst,0,sizeof(isFirst));
        memset(length,0,sizeof(length));
        
        //건물의 갯수와 건설 규칙 순서 
        scanf("%d %d",&n,&k);
        //각 건물 0번 인덱스에 건물의 건설 시간을 저장한다. 
        for(int i=1;i<=n;i++)
            scanf("%d",&build[i][0]);
       //각 건물의 경로 초기화           
        for(int i=0;i<k;i++){
            scanf("%d %d",&x,&y);
            int a = ++path[x];
            //해당 경로가 있음을 표시하기위해  1을 저장한다. 
            build[x][a] = y;
            //또한 해당 경로가 시작점이 가능한지 아닌지도 체크를 해야된다.
            isFirst[y] = 1; 
        } 
        //목표 건물 
        scanf("%d",&w);
        printf("%d\n",bfs());       
    } 
}

변수가 쓸대 없이 많아진 것 같아 나중에 시간을 내서 리팩토링을 해야겠단 생각이 든다.

정답률이 15%라 엄청 긴장하고 풀었는데 그 정도 까지의 문제는 아니었던 것 같다.