[백준] 2252 줄세우기, C++

2252번: 줄 세우기

문제 요약

비교 상태를 사용하여 줄 세우기, 위상 정렬

접근

1. 트리

트리를 생성한다음 최상위 노드에서 후위 순회하는 방식으로 접근했다.
이 접근방식을 구현할때 반례가 바로 떠올라 안될거같아서 적당히 구현했다.

#define MAX_SIZE 32000

int visit[MAX_SIZE + 1]; // 128kb
int parent[MAX_SIZE + 1]; // 128kb

void postorder(int index, const vector<vector<int>>& son)
{
    if (visit[index])
        return;
    visit[index] = 1;
    for (auto s: son[index])
    {
        postorder(s, son);
    }
    cout << index << " ";
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<int>> son(N + 1);

    for (size_t i = 0; i < M; i++)
    {
        int s, p;
        cin >> s >> p;
        parent[s] = p;
        son[p].push_back(s);
    }
    for (size_t i = 1; i <= N; i++)
    {
        if (visit[i]) continue;
        postorder(i, son);
    }
    cout << endl;
    return 0;
}

2. 위상정렬 1 - 진입차수 방식

위상 정렬에 대해 아예 몰라서 찾아보았다.
비순환 방향 그래프를 순서에 거스르지 않게 나열한 그래프이다. 순서만 지키면 되기때문에 하나의 비순환 방향 그래프에서 여러개의 위상정렬이 나올수 있다.

비순환 방향(유향) 그래프를 위상정렬 그래프로 만드는 알고리즘은 여러개가 있는데 진입차수 방식과 DFS방식에 대해서 알아보았다.

진입차수(in degree) 방식 (BFS와 유사함)

1. 입력에 대해서 각 정점마다 들어오는 간선 수를 저장한다.
   1. 배열(indegree)을 사용해서 진입차수를 저장한다.
2. 진입차수가 0인 정점에 방문 체크를 하고, 해당 정점을 Queue에 추가한다.
3. Queue에 추가한 정점에 대해 인접한 정점을 모두 방문하고, 해당 정점의 진입차수 값을 1 감소시킨다.
4. 모든 인접 정점을 방문하면 해당 정점은 Queue에서 제거하고 vector에 추가한다.
5. Queue가 빌때까지 2~4를 반복한다.
6. 4의 vector를 순서대로 읽는다.

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

#define MAX_SIZE 32000

int visit[MAX_SIZE + 1]; // 128kb
int inDegree[MAX_SIZE + 1]; // 128kb

int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<int>> adjList(N + 1);

    for (size_t i = 0; i < M; i++)
    {
        int s, e;
        cin >> s >> e;

        inDegree[e] += 1;
        adjList[s].push_back(e);
    }

    queue<int> q;
    vector<int> answer;
    for (size_t i = 1; i <= N; i++)
    {
        if (inDegree[i] == 0)
        {
            visit[i] = 1;
            q.push(i);
        }
    }
    while (!q.empty())
    {
        int cur = q.front();
        answer.push_back(cur);
        q.pop();
        for (auto adj: adjList[cur])
        {
            if (visit[adj]) continue;

            inDegree[adj] -= 1;
            if (inDegree[adj] == 0)
            {
                q.push(adj);
                visit[adj] = 1;
            }
        }
    }

    for (auto ans: answer)
    {
        cout << ans << " ";
    }
    cout << endl;
    return 0;
}

3. 위상정렬 2 - DFS 방식

재귀함수를 사용하는 DFS 방식은 다음과 같다.

1. 한 정점에서 시작해서 방문표시를 하며 다른 정점을 방문한다.
2. 마지막 부분에 도달하면(더이상 갈 정점이 없으면) 빠져나오면서 해당 정점을 deque(double ended queue)의 앞에 추가한다. (vector의 뒷부분에 저장해도 된다.)
3. 모든 정점을 방문할때까지 1~2를 반복한다.
4. 앞에 추가했으면(deque로 저장했으면) 순서대로, 뒤에 추가했으면(vector에 저장했으면) 역방향으로 값을 읽는다.

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

#define MAX_SIZE 32000

int visit[MAX_SIZE + 1]; // 128kb
vector<int> answer;

void dfs(int index, const vector<vector<int>>& adjList)
{
    visit[index] = 1;
    for (auto adj: adjList[index])
    {
        if (visit[adj]) continue;
        dfs(adj, adjList);
    }
    answer.push_back(index);
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<int>> adjList(N + 1);

    for (size_t i = 0; i < M; i++)
    {
        int s, e;
        cin >> s >> e;
        adjList[s].push_back(e);
    }

    for (size_t i = 1; i <= N; i++)
    {
        if (visit[i]) continue;
        dfs(i, adjList);
    }

    for (auto it = answer.rbegin();
             it != answer.rend(); ++it
    )
    {
        cout << *it << " ";
    }
    cout << endl;

    return 0;
}

새로 알게된 것

1. 위상정렬의 두가지 방법
2. 타입을 추론할수 있는 auto는 편하다
   vector<int>::reverse_iterator it = a.begin() 이라고 작성할걸 auto it = answer.rbegin()로 작성할수 있다.

참고
https://yoongrammer.tistory.com/86