BOJ 2252 줄 세우기

www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

연결관계를 파악하기 위해서 graph가 필요하였고, 이를 어떻게 사용해야지 같은 graph에 속한 node간의 선후관계를  파악할 수 있을지 고민하였다.

그래프를 그려보니 가장 첫번째에 줄을 설 수 있는  node는 부모가 없음을 확인하였다.

그 노드를 지워보니 두번째에 줄을 설 수 있는 node들의 후보군들도 부모가 없음을 확인하였다.

여기서 부모가 없는 node를 줄을 세우고 제거 한 뒤, 다시 부모가 없는 node를 찾아 출력을 해가면 되겠다고 생각을하였다.

 

두개 이상의 독립된 그래프에서도 서로 다른 그래프의 node끼리는 순서에 영향을 미치지 않으므로, 위의 풀이가 맞다고 생각하였고, 그대로 구현하였다.

아래 코드는 제출 코드이다.

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

int n,m;
int indgree[32001];
vector<vector<int>> graph;


int main(){
    scanf("%d%d",&n,&m);
    graph.resize(n+1);
    for(int i=0;i<m;i++) {
        int a, b;
        scanf("%d%d",&a,&b);
        graph[a].push_back(b);
        indgree[b]++;
    }

    queue<int> q;
    for(int i=1;i<=n;i++){
        if(!indgree[i]){
            q.push(i);
        }
    }
    /*
    while(q.size()){
        int qsize = q.size();
        while(qsize--){
            int now = q.front();
            printf("%d ",now);
            q.pop();
            for(int next : graph[now]){
                if(indgree[next] == 0) continue;
                indgree[next]--;
                if(indgree[next] == 0) q.push(next);
            }
        }
    }
    */
    
    while(q.size()){
        int now = q.front();
        printf("%d ",now);
        q.pop();
        for(int next : graph[now]){
            if(indgree[next] == 0) continue;  // 혹시 모를 underflow defense
            indgree[next]--;
            if(indgree[next] == 0) q.push(next);
        }
    }
    
    return 0;
}

 

처음에는 첫번째 node 후보군, 두번재 node 후보군을 나눠야하나 생각했지만, depth 를 따지지 않으므로 없애도 상관없다고 생각했다.

문제 풀이 중에 indgree는  음수가 될 경우는 정말 드물지만, 혹시 몰라서 defence code를 추가하였다.