백준 문제 2252번 줄 세우기 문제풀이 c++

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

2252번: 줄 세우기

 

문제해석

 

위상정렬 문제인데 dfs를 사용한 위상정렬로 코드를 작성하였다.

dfs로 위상정렬을 할 경우 역순으로 출력해야한다.

답이 여러가지인경우 아무거나 출력하면되기 때문에 좀 수월했다.

만약 여러 답중 사전순으로 가장 앞선 것을 출력을 요구하면 우선순위큐를 사용한 bfs 위상정렬로 풀어야 했을 것 같다.

 

먼저 입력이 들어온대로 방향 그래프를 만들어준 후에 시작점이 여러개가 되는 경우가 대부분인데 이걸 어떻게 할지를 고민 했다.

 

4 2

4 2

3 1

입력이 위 처럼 들어왔을 때 그래프가 아래와같다.

 

시작점이 3번도 될 수 있고 4번도 될 수있는데 애초에 시작점인가?를 매번 판단하는것을 어떻게 구현할지 고민하다가 문제에서 정점은 1번부터 N번까지라고 명시 되어있는 것 을 발견하였다.

 

따라서 0점 정점을 임의로 만들어서 1 2 3 4를 순서대로 방향 그래프로 이어주면 아래 그림 처럼된다.

 

더 이상 갈수있는 경로가 없으면 벡터 u에 넣는다.

0번정점에서 dfs를 돌리면 벡터 u에는 순차적으로 1 2 3 4 0이 들어가있다.

역순 출력을 해야하니 0 4 3 2 1이고 0번은 임의로 넣은 것이므로 이걸 제외하고 출력해주면 4 3 2 1이 나온다.

이건 여러 답중 하나에 해당한다.

 

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
typedef long long int ll;
using namespace std;
void dfs(int n);
vector <int> v[32001];
vector <int> u;
bool visited[32001];
int main(){
    cout.tie(NULL);
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int n,m; cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        v[0].push_back(i);
    }
    for(int i=0; i<m; i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
    }
    dfs(0);
    for(int i=u.size()-2; i>=0; i--)
    {
        cout<<u[i]<<" ";
    }
}
void dfs(int n){
    if(v[n].size()==0)
    {
        u.push_back(n);
        return;
    }
    for(int i=0; i<v[n].size(); i++)
    {
        if(visited[v[n][i]]==0)
        {
            visited[v[n][i]]=1;
            dfs(v[n][i]);
        }
    }
    u.push_back(n);
}