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

---

문제 이해 단계

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

2252번: 줄 세우기

---

문제 접근 단계

1번부터 ~N번까지 N명의 학생들을 키 순서대로 줄을 세운다.

입력을 키를 비교한 두 학생의 번호 A, B가 M개 들어온다.
이는 A학생 뒤에 B학생이 서야 한다는 의미이다.

학생들을 앞에서부터 줄을 세운 결과를 출력하는데,
답이 여러 가지인 경우에는 아무거나 하나 골라서 출력한다.

 

 

---

문제 구현 단계

일단 제한사항부터 살펴보자.

학생의 수 N은 최대 32,000까지 가능하다.
그리고 키를 비교한 횟수 M은 최대 100,000까지 가능하다.

만약 최악의 경우, N*M = 10^9 정도이기 때문에 시간초과가 나온다.
따라서 M개의 연관관계와 N명의 학생을 모두 비교하는 것은 안된다.

 

---

연관관계의 특징

이 문제에서 논리적으로 생각해봐야 할 것이 있다.
여기서 M이 뜻하는 바가 무엇인가에 대해서 이다.

M개의 줄에는 두 학생의 번호 A, B가 들어오는데,
이는 A가 B앞에 서야 한다는 것을 의미한다.

만약 이런 식으로 된다고 가정하자.

A B
B C
C A

이게 과연 말이 될까?

C보다 앞에 있어야 하는 B,
B보다 앞에 있어야 하는 A,
근데 C는 A보다 앞에 있어야 한다? 모순된다.

따라서 이 문제가 성립하기 위해서는 위와 같은 사이클이 발생해서는 안된다.

 

---

비순환 방향 그래프(DAG)

사이클이 발생하지 않는 그래프를 우리는 비순환 방향 그래프라고 부른다.
여기서 주어지는 그래프는 비순환 방향 그래프이다.

그리고 문제에서 구하라고 한 것은 앞에서부터 줄을 세운 결과,
즉 우선순위에 따라 번호를 출력하는 것이다.

여기에 딱 어울리는 알고리즘이 있다.
비순환 방향 그래프일 때 사용할 수 있는 알고리즘인데,
모든 간선에 대해 정점 u가 정점 v보다 먼저 오는 순서로 정렬시킨다.

즉, 우선순위대로 정렬해 준다는 소리이다.
이 문제에서는 찰떡이다.

 

---

위상 정렬 방법

해당 문제에서 위상 정렬을 하는 방법에 대해 적어보면 이렇다.

A B
C B
라고 입력이 주어졌다고 치자.
그럼 B는 A와 C 뒤에 있어야 한다.

이를 우선순위로 포함한다면?
A가 B앞에 왔을 때 우선순위가 한번 밀렸고,
C가 B 앞에 왔을 때 또 한 번 우선순위가 한번 밀렸다.

즉 B의 우선순위 = 2이다.
여기서 A가 출력되면 B의 우선순위에서 -1을 해주고
C가 출력되면 C의 우선순위에서 -1을 해준다.

그렇게 B의 우선순위  = 0이 되면 그 즉시 B를 출력해 준다.

이런 원리를 통해 모든 번호를 출력하면 된다.

맨 처음에는 우선순위가 0인 것부터 출력을 시작하면 된다.
그리고 거기에 연결된 번호의 우선순위를 -1을 한다.

마지막으로 그 번호의 우선순위가 0이 되면 큐에 넣고 이를 출력해 준다.

자세한 과정은 문제 구현 단계에서 코드로 보자.

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

int N,M;

vector<int> back[32001]; // 각 번호의 관계 back[A] = {B,C} -> A 뒤에 B,C가 있다.
int priority[32001] = {0,}; // 각 번호의 우선순위 저장
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

    queue<int> q;
    cin >> N >> M;
    for(int i = 0; i < M; i++){
        int first, second;
        cin >> first >> second;
        back[first].push_back(second);
        priority[second]++; // 두번째로 언급될때마다 해당 번호를 우선순위를 한칸씩 미룸
    }
    for(int i = 1; i <= N; i++){
        // 우선순위가 0인 것부터 큐에 넣음
        if(priority[i] == 0) {
            q.push(i);
        }
    }

    while(!q.empty()){
        int x = q.front();
        q.pop();
        cout << x << " "; // 큐에서 뺀 것을 출력

        // 해당 번호 뒤에 있는 것들 나열
        for(int i = 0; i < back[x].size(); i++){
            int nx = back[x][i];
            priority[nx]--; // 해당 번호 뒤에 있는 것들의 우선순위 -1

            // 우선순위가 0이 되면 큐에 넣음
            if(priority[nx] == 0) {
                q.push(nx);
            }
        }
    }
}

이 위상정렬 방식에서는 BFS를 기본 베이스로 사용한다.
priority 배열에 각 번호의 우선순위를 저장해 둔다.

그리고 priroity가 0인 것부터 큐에 넣은 다음
그에 연결된 번호의 우선순위를 -1씩 하는 것을 반복한다.

그 번호의 우선순위가 0이 되면 그것을 큐에 넣는다.
이를 큐가 빌 때까지 반복한다.

로직 자체는 복잡한 것이 없었다.
나머지는 주석으로 읽어보면 충분히 이해가 될 것 같다.

이만 풀이를 마치겠다.

 

 

---

시행착오

위상정렬 알고리즘을 처음 알았다.
예전부터 사용했었는지는 모르겠는데, 알고리즘에 대해 알고 정식적으로 사용해 본 것은 처음이다.

이게 비순환그래프에서 사용가능한지에 대해서는 또 처음 알았네

역시 알고리즘은 배울게 많아.

생활비..

https://toss.me/howudong

howudong님에게 보내주세요