백준 2252번 [줄 세우기](C++) -yes6686- 티스토리

백준 문제 풀이: 2252 [줄 세우기]

---

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

문제 설명:

학생들의 키 순서를 일부 비교한 결과를 바탕으로 전체 학생을 줄 세우는 문제입니다. 주어진 간선을 통해 위상 정렬(Topological Sorting)을 수행해야 합니다.

• 각 학생은 번호로 표현되며, 총 학생의 수는 n입니다.
• 각 비교는 (a, b) 형태로 주어지며, 이는 학생 a가 학생 b보다 앞에 있어야 함을 나타냅니다.
• 이 정보를 바탕으로 학생들을 키 순서대로 나열합니다.

---

문제 해결 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> v[32001];
queue<int> q;
int inDegree[32001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        inDegree[y]++;
    }

    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int k = q.front();
        q.pop();
        cout << k << ' ';
        for (int i = 0; i < v[k].size(); i++) {
            int j = v[k][i];
            inDegree[j]--;
            if (inDegree[j] == 0) {
                q.push(j);
            }
        }
    }
}

예제

입력:
4 2
4 2
3 1

출력:
3 4 1 2

---

코드 설명

• 그래프 생성: 입력을 바탕으로 방향성 있는 그래프를 생성합니다. 각 간선은 학생의 비교 관계를 나타냅니다.
• 진입 차수 계산: 각 학생에 대해 진입 차수를 계산합니다.
• 위상 정렬:
  • 진입 차수가 0인 학생을 큐에 삽입합니다.
  • 큐에서 학생을 하나씩 꺼내고, 해당 학생의 간선을 제거합니다. 이 과정에서 진입 차수가 0이 된 학생은 큐에 추가합니다.
  • 모든 학생을 방문할 때까지 이 과정을 반복합니다.

시간 복잡도

• 그래프 생성: O(m), 간선의 수에 비례.
• 위상 정렬: O(n + m), 정점과 간선의 합에 비례.

---

결과

이 코드는 위상 정렬 알고리즘을 이용하여 주어진 조건에 따라 학생을 정확히 정렬합니다. 입력 조건을 만족하는 경우 항상 유효한 정렬 결과를 출력합니다.