백준(BOJ) 2252번 줄 세우기

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

문제

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

나의풀이 :

DFS를 이용한  위상 정렬로 문제를 풀어 보았다. 

1~N까지 dfs가 종료하는 순서를 기록한 뒤 이 순서를 뒤집는다. 그래프에 사이클이 없다면 이 순서는 그래프의 위상 정렬 결과가

될 것. 

코드 ( C ++ ) 

#include <iostream>

#include <algorithm>

#include <cstring>

#include <vector>

using namespace std;

int N, M;

const int MAX = 32000 + 1;

vector<int> adj[MAX];

bool check[MAX];

vector<int> order;

vector<int> result;

void dfs(int i)

{

check[i] = true;

for (int next = 0; next < adj[i].size(); ++next)

{

if (check[adj[i][next]] == false && adj[i][next] != 0)

dfs(adj[i][next]);

}

order.push_back(i);

}

int main()

{

cin >> N >> M;

for (int i = 0; i < M; ++i)

{

int n1, n2;

cin >> n1 >> n2;

adj[n1].push_back(n2);

}

// adj에 주어진 그래프를 위상정렬한 결과를 반환한다.

memset(check, 0, sizeof(check));

order.clear();

for (int i = 1; i <= N; ++i)

if (!check[i])

dfs(i);

reverse(order.begin(), order.end());

for (int i = 0; i < order.size(); ++i)

cout << order[i] << " ";

return 0;

}