[백준 2252] 줄세우기

문제풀이

위상정렬 공부후 적용을 위해 푼 문제이다.

 

자료구조에서 위상정렬을 배울 때는 연결리스트를 만들어 사용하였지만. 벡터를 알고있으니 이차원 벡터를 사용한다.

 

graph[from].push(to);

 

input이 들어올때마다 저렇게 추가해준다. 그리고 to기준으로 indegree를 추가할때마다 1씩 증가시켜준다.

 

indegree가 0인 것을 먼저 큐에 삽입한다.

 

하나씩 빼면서 출력하고 from이 가리키는 to의 indegree를 줄이고 연결도 지워나간다. (-> 위상정렬에서 삭제하는 과정)

계속 반복한다. 언제까지? 큐가 빌때까지

소스코드

w

#include <stdio.h>
#include <vector>
#include <queue>
 
using namespace std;
 
int N, M;
 
queue<int> q;
vector<vector<int>> graph;
vector<int> cnt_indegree;
int main() {
    
    scanf("%d %d",&N,&M);
    
    graph.assign(N+1, vector<int>(0,0));
    cnt_indegree.assign(N+1, 0);
    for(int i=0;i<M;i++){
        int from,to;
        scanf("%d %d",&from,&to);
        graph[from].push_back(to);
        cnt_indegree[to]++;
    }
    
    for(int i=1;i<=N;i++){
        if(cnt_indegree[i]==0)
            q.push(i);
    }
    
    while(!q.empty()){
        int node = q.front();
        q.pop();
        printf("%d ",node);
        for(int i=0;i<graph[node].size();i++){
            cnt_indegree[graph[node][i]]--;
            if(cnt_indegree[graph[node][i]]==0){
                q.push(graph[node][i]);
            }
        }
        graph[node].clear();
    }
    
    return 0;
}
 

문제 링크 : https://www.acmicpc.net/problem/2252

2252번: 줄 세우기