[C++] 1005번 ACM Craft - DP, 위상 정렬, DFS

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

#define MAX_BUILDING 1001
#define MAX_ROUTE 100001

using namespace std;

int T, N, K;  //테스트케이스의 개수 T, 건물의 개수 N, 건설 순서 규칙의 개수 K
int t[MAX_BUILDING];  //건설에 걸리는 시간
vector<int> r[MAX_ROUTE];  //건설 작업 루트
int inDegree[MAX_BUILDING];  //진입 차수
int res[MAX_BUILDING];  //위상 정렬 결과
int dis[MAX_BUILDING];  //앞에서부터 건설하는데 까지 걸리는 시간

void topologySort()  //위상 정렬
{
    queue<int> q;
    
    for(int i=1; i<=N; i++) {
        if(!inDegree[i]) q.push(i);  //진입 차수가 0인 것을 큐에 삽입
    }
    
    for(int i=0; i<N; i++) {
        int x = q.front(); q.pop();
        res[i]=x;
        for(int j=0; j<r[x].size(); j++) {
            int y = r[x][j];  //새롭게 진입 차수가 0이 된 정점 큐에 삽입
            if(!(--inDegree[y])) q.push(y);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> T;
    for(int i=0; i<T; i++) {
        for(int j=0; j<=N; j++)
            r[j].clear();  //배열, 벡터 초기화
        memset(dis, 0, (N+1)*sizeof(int));
        
        cin >> N >> K;
        for(int j=1; j<=N; j++)
            cin >> t[j];
        int X, Y;  //X->Y로 건설 가능
        for(int j=0; j<K; j++) {
            cin >> X >> Y;
            r[X].push_back(Y);
            inDegree[Y]++;  //진입 차수 1+
        }
        int W;  //마지막 건설 건물
        cin >> W;
        
        topologySort();  //위상 정렬
        
        for(int j=0; j<N; j++) {
            for(int k=0; k<r[res[j]].size(); k++) {
                int pre = res[j];
                int next = r[res[j]][k];
                
                if(t[pre] + dis[pre] > dis[next])  //현재 이동거리가 다음 목표까지의 거리보다 크면 갱신
                    dis[next]=t[pre]+dis[pre];
            }
        }
        cout << dis[W]+t[W] << '\n';
    }
    
    return 0;
}

위상정렬이라는 게 처음 나와서 새로 공부했다. 쉬었다가 다시 공부하려니까 백터 매소드도 기억이 안나서 복습했는데 아무튼 내가 이 문제를 풀면서 찾아봤던 사이트를 아래에 적어놨다.

 

나는 위상정렬로 풀어 160ms가 나왔는데 다른 사람의 코드를 보니까 위상 정렬이 아니라 BFS로 풀어서 더 빨리 푼 경우도 있었다. 위상 정렬을 썼을 때에는 DP를 한 번더 써줘야됬었는데 BFS로 푸니까 바로 나와서 조금 신기하기는 했다.

 

 

 

<위상 정렬>

https://m.blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)

 

<vector method>

https://blockdmask.tistory.com/70

[C++] vector container 정리 및 사용법

 

<BFS로 푼 코드(풀어야 볼 수 있습니다.>

https://www.acmicpc.net/source/18541227

로그인

 

 

 

 

 

※현재 고등학교 등교중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.