[백준/c++] 2252번: 줄 세우기

 

 

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

 

문제 요약

 

N명의 학생들을 키 순서대로 줄을 세우자. 

두 학생의 키를 비교하는 방법으로 사용한다. 

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성해보자.

 

 

범위

 

학생 수 N(1 ≤ N ≤ 32,000), 키를 비교한 횟수 M(1 ≤ M ≤ 100,000)

 

 

 

---

 

 

 

💡 위상 정렬이란?

 

 

 

Directed Acyclic Graph(DAG)

 

- 간선에 방향성이 존재한다

- 사이클이 없다

 

 

위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다.

위상 정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다.

 

출처: https://ko.wikipedia.org/wiki/위상정렬

 

 

 

---

 

 

 

1. 정점들의 Indegree 계산하기 (해당 정점으로 들어오는 간선의 개수)

2. 들어오는 간선이 0개(Indegree [i] == 0)인 정점을 찾아 Q(queue)에 넣기

3. while(! q.empty())

    1) Q에서 정점 x를 꺼내 정렬

    2) Graph에서 x 제거 (x와 연결된 애들도 업데이트)

    3) 새롭게 정렬 가능한 정점을 찾아 Q에 넣기

 

 

벡터 graph를 만들어주는데, 이때 위상 정렬이므로 간선에 방향성이 있기 때문에 graph [b]. push_back(a); 주의하자

 

 

#include <iostream>
#include <queue>
#include <vector>
#define MAX 32002
using namespace std;
int n, m, a, b, indegree[MAX];
vector<int> graph[MAX];
queue<int> q;

void input(){
    cin >> n >> m;
    for(int i=0; i<m; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        indegree[b]++;          //들어오는 간선 개수 카운팅
    }
}

void solution(){
    for(int i=1; i<=n; i++) if(indegree[i] == 0) q.push(i); //들어오는 간선이 0개인 정점, 큐에 넣기
        
    while(!q.empty()){
        int x = q.front();
        q.pop();                            //x 꺼내기
        cout << x << ' ';
        for(int j : graph[x]){              //graph에서 x 와 연결된 애들을 찾아서 제거해줘야 함
            indegree[j]--;                  //들어오는 간선 개수 --
            if(indegree[j] == 0) q.push(j); //새로운 정점, 큐에 삽입
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}

 

 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!