[백준/C++] 2252번 줄 세우기 (Topology sort)

문제 해석

---

---

문제 풀이

---

코딩테스트 준비하면서 위상 정렬은 알고 있어야지~ 싶어서 한 문제 풀려고 찾아본 문제이다.

위상 정렬이 기억나지 않아 푸는데 좀 헤맸다.

 

문제 풀이에 들어간 내 의식의 흐름은 아래와 같다.

1. 우선 배열(인접행렬)로 생성하면 3만 x 3만으로 128MB는 훌쩍 넘어 터질 것 같아 인접리스트(adjacency list) 형태로 구현하였다.
   
   
2. 만약 한 번도 누군가의 뒤에 선다는 정보가 없었던 사람이 있다면 모두 큐에 넣어주고 순서대로 출력하면 되겠다 싶었으나
   (반례: 4,4   1->2   2->3   4->3   4->1  형태로 준다면 단순 bfs로는 해결할 수 없고 응용해야한다는 것을 알게 되었다.
   
   
3. bfs에서 생기는 반례는 결국 내 이전 작업이 끝나지 않았는데 내가 먼저 queue에 들어가서 생기는 문제였으니 이전 노드가 몇개인지 체크하고 이전 노드가 모드 que에 들어간 이후에 넣어주면 되겠다는 생각을 하였다.
   
   
4. 이후 que에 넣는 순서대로 저장해두고 정답 순서로 출력했다.

---

코   드

---

#include <bits/stdc++.h>
using namespace std ;
int N, M ;
int check[32001] ;

vector<int> order[32001] ;
vector<int> answer ;

void BFS()
{
    queue<int> que ;

    for(int i = 1 ; i <= N ; i++)
        if(check[i] == 0)
        {
            answer.emplace_back(i) ;
            que.push(i) ;
        }
    
    while(!que.empty())
    {
        int front = que.front() ;
        que.pop() ;

        for(int num : order[front])
        {
            check[num]-- ;
            if(check[num] == 0)
            {
                answer.emplace_back(num) ;
                que.push(num) ;
            }
        }
    }
}

int main()
{
    cin >> N >> M ;
    for(int i = 1 ; i <= M ; i++)
    {
        int sp, ep ;
        cin >> sp >> ep ;
        check[ep]++ ;
        order[sp].emplace_back(ep) ;
    }

    BFS() ;

    for(int num : answer)
        cout << num << " " ;
}

---

느낀점: 문제 자체가 어렵진 않은데 위상정렬이다! 떠올리고 실수 없이 구현하기까지 얼마나 걸릴까 미지수다.

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

2252번: 줄 세우기