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

2252번: 줄 세우기

[문제 설명]

 

---

[문제 풀이]

이 문제를 풀기전에 위상정렬 알고리즘에 대해 알고 있으면 쉽게 풀 수 있다.

위상정렬 알고리즘에 대해 잘 모른다면 아래 포스트를 읽고오면 푸는데 도움이 될 것이다. 

[Algorithm] - Topology Sort(위상정렬)

위상정렬을 하는 방식에는 BFS(Queue), DFS(Stack) 두가지 방식이 있다.

위 포스트를 읽고, 좀 더 이해가 잘되는 방법으로 풀면 될 것 같다.

 

따로 설명할 것 없이 위상정렬 알고리즘만 적용하면 바로 답이 나오는 문제다.

문제에 나와있는 출력만이 정답이 아니므로 직접 손으로 그려보면서 답이 맞는지 체크해보면 좋을 것 같다.

 

[코드]

[GitHub]

GitHub - EGyeom/ProblemSolving

코드가 깨끗하고 명확하게 보일진 모르겠지만, 누군가에게 도움이 될 수도.. 있기에..

 

BFS 풀이

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

#define INPUTMAX 32001
int input;
vector<int> edgeInfo[INPUTMAX],inDegree(INPUTMAX,0);

void topologySort(vector<int> indegree)
{
    queue<int> q;
    
    for(int i = 1; i <= input; i++)
    {
        if(inDegree[i] == 0)
            q.push(i);
    }

    while(q.empty() == false)
    {   
        int front = q.front();
        q.pop();
        cout << front << " ";
        for(int& edge : edgeInfo[front])
        {
            if(--inDegree[edge] == 0)
                q.push(edge);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n,m;
    cin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        int a,b;
        cin >> a >> b;
        edgeInfo[a].push_back(b);
        inDegree[b]++;
    }

    input = n;
    topologySort(inDegree);
}

 

DFS 풀이

#include <bits/stdc++.h>
using namespace std;


#define INPUTMAX 32001

int input;
stack<int> st;
vector<int> isVisited(INPUTMAX,0);
vector<int> edgeInfo[INPUTMAX];

void dfs(int curr)
{
    isVisited[curr] = true;
    for(int& iter : edgeInfo[curr])
    {
        if(isVisited[iter] == false)
        {
            dfs(iter);
        }
    }
    st.push(curr);
}

void topologySort_dfs()
{    
    for(int i = 1; i <= input; i++)
    {
        if(isVisited[i] == false)
        {
            dfs(i);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int n,m;
    cin >> n >> m;

    for(int i = 0; i < m; i++)
    {
        int a,b;
        cin >> a >> b;
        edgeInfo[a].push_back(b);
    }

    input = n;

    topologySort_dfs();
    while(st.empty() == false)
    {
        cout << st.top() << " ";
        st.pop();
    }
}