Gidhub BE Developer

BOJ - 음악 프로그램

2018-01-29
goodGid

Problem

Problem URL : 음악 프로그램

Screenshots of Problem Explain

Code


#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> v;
int size[1001];

int main(){
    int n,m;
    cin >> n >> m;
    v.resize(n+1);
    
    for(int i=0; i<m; i++){
        int cnt;
        cin >> cnt;
        
        int a,b;
        scanf("%d",&a);
        
        for(int i=0; i<cnt-1; i++){
            scanf("%d",&b);
            v[a].push_back(b);
            size[b]++;
            a=b;
        }
    }
    
    queue<int> q;
    for(int i=1; i<=n; i++){
        if(size[i] == 0)
            q.push(i);
    }
    
    int node_cnt = 0;
    vector<int> print_v;
    
    while (! q.empty()) {
        node_cnt ++;
        int top = q.front();
        q.pop();
        print_v.push_back(top);
        
        int _size = (int) v[top].size();
        for(int i=0; i<_size; i++){
            size[ v[top][i] ] --;
            if( size[ v[top][i] ] == 0)
                q.push(v[top][i]);
        }
    }

    if( node_cnt == n){
        for(int i=0; i<print_v.size(); i++)
        printf("%d\n",print_v[i]);
    } else{
        cout << "0" << endl;
    }
    
    return 0;
}





Feed Back

  • 위상 정렬(topological sort) 관련 문제 !

  • 코드 틀이 있는 듯한 알고리즘인거 같다.

  • 코드 ReFactoring을 하지 않았다. 즉 Clean Code는 아니다 ㅎㅎ


Comments

Content