bt[next] 를 해주고 첫 노드 방문 처리를 main 해서 해준 게 포인트

//백준 1005
// 만들어야 하는 건물 에서 dfs 해서 제일 시간 오래 걸리는 곳 까지 탐색
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
int fb;//final building
int bt[1010]; //build time
//vector<int> adj[1010];
vector<int> adj[501];
int dp[1010];
bool ch_fb = false;
bool visited[1001];
vector<int> order;
int dfs(int x) {
        int& ret = dp[x];
        if (ret != -1) {
               return ret;
        }
        ret = 0;
        for (int i = 0; i < adj[x].size(); ++i) {
               int next = adj[x][i];
               ret = max(ret,bt[next] + dfs(next));
        }
        return ret;
}
int main(void)
{
        memset(dp, -1, sizeof(dp));
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        int t;
        cin >> t;
        int k1=0;//for input
        for(int i=1;i<=t;++i){
               cin >> k1;
               bt[i] = k1;
               while (1) {
                       cin >> k1;
                       if (k1 == -1) {
                               break;
                       }
                       adj[i].push_back(k1);
               }
        }
        
        for (int i = 1; i <= t; ++i) {
               cout << dfs(i) + bt[i] << '\n';
        }
}

저작자표시 비영리 변경금지

//[위상정렬] 백준 2623 음악 프로그램
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
vector<int> adj[1001];
bool visited[1001];
vector<int> order;
void dfs(int x) {
        visited[x] = true;
        for (int i = 0; i < adj[x].size(); ++i) {
               int next = adj[x][i];
               if (!visited[next]) {
                       dfs(next);
               }
        }
        order.push_back(x);
}
int a, b;
vector<int> topo() {
        order.clear();
        memset(visited, false, sizeof(visited));
        for (int i = 1; i <= a; ++i) {
               if(!visited[i])
                       dfs(i);
        }
        reverse(order.begin(), order.end());
        //사이클 확인하는 코드 좀더 효율적으로 짤 필요
        for (int i = 1; i <= a; ++i) {
               int len = adj[i].size();
               for (int j = 0; j < len; ++j) {
                       int aaa = i, bbb = adj[i][j];
                       bool aa = false;
                       for (int k = 0; k < order.size(); ++k) {
                               if (aaa == order[k]) {
                                      aa = true;
                               }
                               if (aa == false && order[k] == bbb) {
                                      return vector<int>();
                               }
                       }
                       aa = false;
               }
        }
               
        return order;
}
int main(void) {
        cin >> a >> b;
        for (int i = 0; i < b; ++i) {
               int aa;
               int bb, cc;
               cin >> aa;
               if (aa == 1) {
                       cin >> aa;//받고 아무것도 안해도 된다.
               }
               else {
                       cin >> bb;
                       for (int j = 0; j < aa-1; ++j) {
                               cin >> cc;
                               adj[bb].push_back(cc);
                               bb = cc;
                       }
               }
        }
        vector<int> ans = topo();
        if (ans.size() == 0) {
               cout << 0;
               return 0;
        }
        for (int i = 0; i < ans.size(); ++i) {
               cout << ans[i] << '\n';
        }
        return 0;
}

저작자표시 비영리 변경금지

// [DFS] 백준 11403 경로찾기
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int adj[101][101];
int ans[101][101];
bool visited[101];
int n;
bool first_on;
void dfs(int x,int first) {
        if (first == x && first_on) {
               ans[x][x] = 1;
        }
        else {
               first_on = true;
        }
        visited[x] = true;
        for (int i = 1; i <= n; ++i) {
               if ((!visited[i] || first == i) && adj[x][i] == 1) {
                       dfs(i,first);
               }
        }
}
int main(void) {
        cin >> n;
        for (int i = 1; i <= n; ++i) {
               for (int j = 1; j <= n; ++j) {
                       cin >> adj[i][j];
               }
        }
        for (int i = 1; i <= n; ++i) {
               for (int j = 1; j <= n; ++j) {
                       memset(visited, false, sizeof(visited));
                       first_on = false;
                       dfs(i,i);
                       if (visited[j]) {
                               if (i != j) {
                                      ans[i][j] = 1;
                               }
                       }
               }
        }
        for (int i = 1; i <= n; ++i) {
               for (int j = 1; j <= n; ++j) {
                       cout << ans[i][j] << ' ';
               }
               cout << '\n';
        }
        return 0;
}

저작자표시 비영리 변경금지

+ Recent posts

티스토리툴바