[백준알고리즘] 1005번 ACM Craft

https://www.acmicpc.net/problem/1005

나의 코드는 2차원배열 때문에 쓸데없이 반복문을 많이 돌아야해서 trash 코드이다..하하..

처음에 푸는 것을 접근은 제대로 한 것 같은데 정확히 어떤 방식으로 해야할지 감이 잡히지 않아서 알고리즘 분류를 봤더니 ?위상정렬? 이라고 쓰여있어서 위상정렬이 뭔지 찾아보았다 ㅠㅠ

http://blog.naver.com/PostView.nhn?blogId=kks227&logNo=220620723528&parentCategoryNo=&categoryNo=&viewDate=&isShowPopularPosts=false&from=postView

위의 블로그에 상세히 설명이 되어있다! 너무너무 친절하시고 똑똑하신분 ㅠㅠ본받고싶닷..

그림 설명 보고 따라서 만들어 봤는데 코드가 너무너무 다른 것..ㅎ.. 공부 열심히 해야징...

<나의 코드>

https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_1005/BOJ_1005.cpp

#include<iostream>
#include<queue>
using namespace std;
 
int main(void)
{
    int T, N, K, delay_time, start, end, goal;
 
    cin >> T;
    while (T--)
    {
        queue<int> q;
        int delay[1001];
        int vertex_ans[1001] = { 0 };
        bool v[1001][1001] = { 0 };
 
        cin >> N >> K;
 
        for (int i = 1; i <= N; i++)
        {
            cin >> delay_time;
            delay[i] = delay_time;
        }
 
        for (int i = 0; i < K; i++)
        {
            cin >> start >> end;
            v[start][end] = 1;
        }
        cin >> goal;
 
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (v[j][i]) break;
                else if (j == N) {
                    q.push(i); vertex_ans[i] = 0;
                }
            }
        }
 
        while (!q.empty())
        {
            int prev_vertex;
            int qsz = q.size();
            int max_delay = 0;
            while (qsz--)
            {
                prev_vertex = q.front();
                q.pop();
 
                if (prev_vertex == goal) break;
 
                for (int i = 1; i <= N; i++)
                {
                    if (v[prev_vertex][i])
                    {
                        v[prev_vertex][i] = 0;
 
                        int new_delay_time = vertex_ans[prev_vertex] + delay[prev_vertex];
                        if (vertex_ans[i] < new_delay_time) vertex_ans[i] = new_delay_time;
 
                        for (int j = 1; j <= N; j++)
                        {
                            if (v[j][i]) break;
                            else if (j==N){
                                q.push(i);
                            }
                        }
                    }
                }
            }
            if (prev_vertex == goal) break;
        }
        cout << vertex_ans[goal] + delay[goal] << '\n';
    }
 
    return 0;
}