C++ 백준 2252 (줄 세우기)

백준 2252 (줄 세우기)

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

2252번: 줄 세우기

---

설명

---

이 문제는 위상정렬(DFS)를 통해 간단히 풀 수 있는 문제였다.

 

위상정렬에 대한 설명은 위상정렬(링크)에 자세히 설명이 되어있다.

 

예제입력으로 각 일에 대한 순서들이 주어지는데

 

각 일을 하나의 노드로 생각하고 방향성이 있는 그래프로 생각하면 된다.

 

예를 들어 1 2 가 입력되었다면 1번노드에서 2번노드로 가는 길이있다고 생각하면 된다.

 

구현

---

 

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int n,m;
int visit[32001];
stack <int> ans;
void dfs(vector <vector<int>> &graph ,int num){
    visit[num]=1;
    for(int i=0;i<graph[num].size();i++){
        int des = graph[num][i];
        if(visit[des]==0) dfs(graph, des);
    }
    ans.push(num);
}

void go(vector <vector<int>> &graph){
    for(int i=1;i<=n;i++){
        if(visit[i]==0) {
            dfs(graph, i);
        }
    }
}


int main(){
    ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    cin>>n>>m;
    vector <vector<int>> g(n+1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        g[a].push_back(b);
    }
    go(g);
    while(!ans.empty()){
        cout<<ans.top()<<" ";
        ans.pop();
    }
    return 0;
}

주의할 점은 각 함수 (go 또는 dfs)에서 인자로 그래프를 받을때 참조를 해줘야 더욱 빠르다. (참조 안하면 시간초과뜸!)

그 이유를 간단히 설명하자면 참조를 하면 새로운 메모리를 사용하지 않고 참조한 데이터의 메모리 주소를 바로 가져오기 때문이당!