2252번

2252번 - 줄 세우기

위상 정렬에 대해서 알아보다가 예제로 풀어본 문제.

위상 정렬이 필요한 경우.. 게임에서 보면 스킬을 1번 찍고, 2번을 찍어야 3번을 찍을 수 있을 때와 같은 상황? 

어떤 작업의 우선순위가 필요한 경우??에 사용된다.

주의할 점은 위상정렬은 DAG(Directed Acyclic Graph) 의 구조에서 사이클이 없을 때 사용가능.

싸이클이 발생하면 우선 순위가 흐려지기 때문

'위상 정렬'을 하는 방법은 2가지가 존재.

1. 한 정점에 들어오는 간선의 수가 0일 때, 큐에 넣음으로서 정렬을 할 수 있다.

2. DFS를 통해서 답을 구할 수 있다.

나는 1번 방법으로 문제를 풀었다.

우선 들어오는 간선의 수가 0인 값들을 큐에 넣어주었다. 그 뒤에 각 정점을 방문하면서 , 그 정점에 들어오는 간선의 수를 하나씩 없애준다.

그러다가 간선의 수가 0이 되는 순간 출력해주고 큐에 넣어주는 방식으로 문제를 풀었다.

2번 방법

DFS를 통해서 끝까지 방문하고 , 리턴 될 때 값들을 stack에 저장하여 역순으로 출력하면 위상정렬이 된다..

( 아직 뭔가 제대로 이해된 게 아니고, 그냥 이렇다라는 공식만 외워서 푼 느낌이다. )

<정답 코드 - 1번 방식>

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
 
int ind[32001];
 
int main()
{
    int N, M;
    vector<int> v[32001];
    queue<int> q;
    cin >> N >> M;
 
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        ind[b]++;
        v[a].push_back(b);
    }
 
    for (int i = 1; i <= N; i++)
    {
        if (ind[i] == 0)
        {
            q.push(i);
        }
    }
 
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        printf("%d ", now);
 
        for (int i = 0; i < v[now].size(); i++)
        {
            int next = v[now][i];
            ind[next]--;
            if (ind[next] == 0)
            {
                q.push(next);
            }
        }
        
    }
 
 
    return 0;
}

<정답 코드 - 2번 방식>

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
 
vector<int> v[32001];
bool visited[32001];
int ind[32001];
stack<int> st;
void dfs(int start)
{
    visited[start] = true;
 
    for (int i = 0; i < v[start].size(); i++)
    {
        int next = v[start][i];
        if (!visited[next])
        {
            dfs(next);
        }
    }
 
    st.push(start);
 
    return;
}
 
int main()
{
    int N, M;
    cin >> N >> M;
 
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        ind[b]++;
    }
 
    for (int i = 1; i <= N; i++)
    {
        if (ind[i] == 0 && !visited[i])
        {
            dfs(i);
        }
    }
    
    while (!st.empty())
    {
        cout << st.top() << " ";
        st.pop();
    }
 
    return 0;
}