Beakjoon] 줄 세우기(백준 2252코테) - 그래프 (C++)

---

🅰️문제주소 : https://www.acmicpc.net/problem/2252

 

🚩문제 

 

 

🪡풀이 

 - 답이 여러 개인 경우가 존재할 수 있으면 위상정렬을 떠올려야 한다 
  (위상정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘)
 - 학생의 키 비교를 2차원 벡터로 map화 하여 저장하고 해당 학생 수만큼 진입차수 배열을 만든다
 - 키 비교가 되었을 경우 비교된 학생의 배열값을 증가시킨다
 - 진입차수가 0인 노드부터 queue에 넣은 뒤 출력시키고 해당 노드가 가리키는 노드의 진입차수 값을 1 감소시킨다 (이때 감소시킨 값이 0 이면 큐에 집어넣는다)
 - 큐 전체가 비어있을 때까지 반복

 

 

☕코드는 아래 숨김

#include <iostream>
#include <vector>
#include <queue>

int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int N, M;
    std::cin >> N >> M;
    std::vector<int> students(N+1, 0);
    std::vector<std::vector<int>> maps(N+1);

    for (int i = 0; i < M; ++i) {
        int f, s;
        std::cin >> f >> s;
        maps[f].push_back(s);
        students[s]++;
    }
    
    std::queue<int> q;
    for (int i = 1; i <= N; ++i) {
        if (students[i] == 0)
            q.push(i);
    }

    while (!q.empty()) {
        int now = q.front();
        q.pop();
        std::cout << now << " ";
        for (int j = 0; j < maps[now].size(); ++j) {
            students[maps[now][j]]--;
            if (students[maps[now][j]] == 0)
                q.push(maps[now][j]);
        }
    }
}

 

💡알게 된 것 

 - 위상정렬은 사이클이 없는 방향그래프에서 순서를 찾기 위해 쓴다
 - 위상정렬의 구현법

---