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

문제

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

---

문제 요약

N명의 학생들을 키 순서대로 줄을 세우려고 한다.

 

각 학생의 키가 주어지지 않고, 두 학생의 키를 비교 결과가 M개 주어졌을 때 줄을 세우는 방법을 출력한다.

 

답이 여러 가지인 경우 아무거나 출력한다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <tuple>
#include <queue>

using namespace std;

int N, M;
vector<int> edges[32032];

// indegree[i]: i번 노드로 들어오는 간선의 수
int indegree[32032];

queue<int> q;

int main() {
    cin >> N >> M;

    // 그래프 입력
    while (M--) {
        // a번 학생이 a번 학생보다 앞에 있다.
        int a, b;
        cin >> a >> b;

        edges[a].push_back(b);
        indegree[b]++;
    }

    // 초기 indegree가 0인 값부터
    for (int i = 1; i <= N; i++) {
        if (indegree[i] == 0) {
            q.push(i);
        }
    }

    while (!q.empty()) {
        int x = q.front();
        cout << x << " ";
        q.pop();

        for (int i = 0; i < edges[x].size(); i++) {
            int y = edges[x][i];
            indegree[y]--;
            if (indegree[y] == 0) {
                q.push(y);
            }
        }
    }

    return 0;
}

---

코드 설명

위상 정렬(Topological Sort)을 이용해 문제를 해결한다.

 

위상 정렬이란 사이클이 없는 방향 그래프에서 각 노드가 하나의 일이라고 생각했을 때, 앞에 일이 끝나야만 뒤에 일이 진행될 수 있는 문제에서 가능한 노드의 순서를 뽑는 방법이다.

 

이 때, 가능한 순서는 유일하지 않다.

 

1. i번 노드에 들어오는 간선의 개수를 저장하는 indegree[i]를 정의한다.

 

2. vector 배열 edges에 그래프 정보를 인접 리스트 형태로 입력 받는다.

+ 이 때, indegree를 증가시키며 초기 값을 설정한다.

 

3. 처음 indegree가 0인 값들을 큐에 넣는다.

 

4. 큐가 빌 때까지 원소를 하나씩 빼면서, 해당 원소(노드)와 인접한 노드의 간선을 제거한다.

+ indegree 값을 감소시키면, 간선 하나가 제거된 것과 같다.

 

5. 원소가 POP되는 순서가 위상 정렬 순서이다.

---

고찰

문제를 보고 그래프를 이용한 문제까지는 생각했지만, 위상정렬을 생각하기는 어려웠다..

관련 문제를 좀 더 풀어봐야겠다.

 

아래 코드는 Greedy로 시도한 코드이다.. (실패)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <tuple>
#include <queue>

using namespace std;

// arr[i]: i번 학생의 줄 위치
int student[32032];
int N, M;

// q[i]: { i번 학생의 줄 위치. i }
priority_queue<tuple<int, int>> q;

int main() {
    cin >> N >> M;

    // 초기 줄 : 1, 2, 3, 4, ...
    for (int i = 1; i <= N; i++) {
        student[i] = i;
    }

    while (M--) {
        // A번 학생이 B번 학생보다 앞에 있다.
        int A, B;
        cin >> A >> B;

        // 이미 A번 학생이 B번 학생보다 앞에 있는 경우
        if (student[A] < student[B]) continue;

        swap(student[A], student[B]);

        for (int i = 1; i <= N; i++) {
            cout << student[i] << " ";
        }
        cout << "\n";

    }

    for (int i = 1; i <= N; i++) {
        q.push({ -student[i], i });
    }

    while (!q.empty()) {
        int stu_i, i;
        tie(stu_i, i) = q.top();
        q.pop();

        cout << i << " ";
    }

    return 0;
}