[백준] 2252 줄세우기

문제 : www.acmicpc.net/problem/2252

2252번: 줄 세우기

분석 :

이 문제는 종만북 DFS BFS 부분의 대표적인 예제 중 위상 정렬에 관한 문제였다.

위상 정렬이란 의존성이 있는 작업이 주어질 때 이를 어떤 순서로 수행해야 하는지 계산한다.

이때 의존 관계를 DAG(사이클 없는 그래프) 로 표현한다. 사이클이 없다는 뜻은 즉 한 방향에서 한 방향으로 흘러가는 꼴의 그래프를 말한다. 그렇기 때문에 기존 DFS BFS 는 트리 노드에 간선을 표시할 때 서로가 서로에 대해 의존하게끔(-> <-) 한 뒤 인접 노드를 탐색하는 것이 일반적이었는데 들어오는 간선 즉 indegree만 확인하면 된다.

indegree가 0이 되면 queue에 push 를 한다. 그리고 q가 비어있지 않을 동안 노드에 indegree가 남아 있다면 for문을 통해 순차적으로 indegree값을 감소시킨다. 다 돌고 indegree가 결국 0 이되면 초기 indegree가 0인 노드를 queue에 넣었던 것처럼 queue에 넣어 준다. 

 

c++ 코드 :

//
//  2252_line.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/08.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>

#define INTMAX 32001

using namespace std;

void line(){
    int N, n;
    //input
    cin >> N >> n;
    queue<int> q;
    vector<int> arr[INTMAX];
    int indegree[N+1];

    for(int i = 0; i < N+1; i++){ // indegree 초기화
        indegree[i] = 0;
    }

    int s1, s2;
    for(int i = 0; i< n; i++){
        cin >> s1 >> s2; // 키 비교한 두 학생
        indegree[s2]++; // 들어온 것만 기록하면 되므로 하나만 저장
        arr[s1].push_back(s2);
    }

    for(int i = 1; i < N+1; i++){//초기 indegree 0 인것 == 검사 대상 
        if(indegree[i] == 0){
            q.push(i); // indegree 0 되면은 q에 push
        }
    }

    while(!q.empty()){
        int temp = q.front(); //1
        q.pop();
        cout << temp << " ";
        for(int i = 0; i < (int)arr[temp].size(); i++){
            indegree[arr[temp][i]]--;
            if(indegree[arr[temp][i]] == 0) q.push(arr[temp][i]);
        }

    }
    cout << endl;

}


int main(){
    line();
    return 0;
}