줄 세우기
BFS로 작성시
#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>
#include<string>
#include<queue>
#include <set>
#include <map>
#include <list>
#include<stack>
#include<deque>
#include<cstring>
#define MAX 26
using namespace std;
int n, m;
vector<vector<bool>> mp;
vector<bool> visited;
vector<int> res;
bool isPure(int idx) {
int counter = 0;
for (int i = 0; i < n; i++) {
if (mp[i][idx])
counter += 1;
}
return !counter;
}
void bfs(int idx) {
visited[idx] = true;
res.push_back(idx);
for (int i = 1; i <= n; i++)
if (mp[idx][i])
mp[idx][i] = false;
}
int main(void) {
cin >> n >> m;
mp = vector<vector<bool>>(n+1, vector<bool>(n+1,false));
visited = vector<bool>(n+1, false);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
mp[a][b] = true;
}
while (true) {
bool breakable = true;
for (int i = 1; i <= n; i++) {
if (!visited[i]&&isPure(i)) {
breakable = false;
bfs(i);
}
}
if (breakable)break;
}
for (int i = 0; i < n; i++) {
cout << res[i] << ' ';
}
cout << endl;
return 0;
}
- 만약 한줄로 줄세워지는 경우, 해당 경우
32000!의 수가 나오므로, 시간 복잡도를 맞출 수가 없음. 골드 버전에서는 좀 더 참신함을 요구함(포켓몬 골드 반만 배우자)
DFS로 작성한 경우
- 확실하게 뒤에 서는 놈이 아무도 없는 경우에, 해당 루트에서 시작하여 앞으로 DFS를 진행하는 방식. 이후 뒤집으면 된다.
#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>
#include<string>
#include<queue>
#include <set>
#include <map>
#include <list>
#include<stack>
#include<deque>
#include<cstring>
#define MAX 26
using namespace std;
int n, m;
vector<vector<bool>> mp;
vector<bool> visited;
vector<int> res;
void dfs(int idx) {
visited[idx] = true;
res.push_back(idx);
for (int i = 1; i <= n; i++) {
if (!visited[i] && mp[i][idx]) {
dfs(i);
}
}
}
int main(void) {
cin >> n >> m;
mp = vector<vector<bool>>(n+1, vector<bool>(n+1,false));
visited = vector<bool>(n+1, false);
vector<bool> isPure(n + 1, true);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
mp[a][b] = true;
isPure[a] = false;
}
for (int i = 1; i <= n; i++) {
if (isPure[i])
dfs(i);
}
reverse(res.begin(), res.end());
for (int i = 0; i < n; i++) {
cout << res[i] << ' ';
}
cout << endl;
return 0;
}
- 여전히 시간초과가 발생한다. 왜그럴까?
- 우선 문제의 제한 조건은
N<32000 and M<100000이다. 위의 두가지 풀이 방법의 경우, 그래프에 대해 간선이 존재하는 경우와 아닌 경우 모두 기록을 해서, 결과적으로 문제가 진행됨에 따라서 N^2으로 문제의 제한 시간인 2초를 넘어갈 수 있는 가능성이 있다. 만약 간선이 하나밖에 없는 희소그래프라고 했을때도, N^2이므로, 복잡한 가지수인 경우에는 당연히 시간 제한을 넘어가게 된다.
- 따라서, 이 경우에는 그래프를 저장하는 방법을 조금 더 달리 하는 것이 좋겠다. 바로, 간선을 저장하는 방식. 무작정 M개를 모두 저장하는 것이 아니라, 각 점마다 연결된 간선 정보를 저장하게 된다면, 최대 시간은 줄어들어 충분히 시간 제한 내로 들어올 수 있게 된다. 해당 방법으로 푼 풀이는 아래와 같다.
#pragma warning(disable:4996)
#include<iostream>
#include<vector>
#include<math.h>
#include<algorithm>
#include <random>
#include<time.h>
#include<string>
#include<queue>
#include <set>
#include <map>
#include <list>
#include<stack>
#include<deque>
#include<cstring>
#define MAX 26
using namespace std;
int n, m;
vector<vector<int>> mp;
vector<bool> visited;
vector<int> nx;
vector<int> res;
void dfs(int idx) {
visited[idx] = true;
res.push_back(idx);
for (int i = 1; i <= n; i++) {
if (!visited[i] && mp[i][idx]) {
dfs(i);
}
}
}
int main(void) {
cin >> n >> m;
mp = vector<vector<int>>(n+1, vector<int>());
visited = vector<bool>(n + 1, false);
nx = vector<int>(n + 1, 0);
for (int i = 0; i < m; i++) {
int a, b; cin >> a >> b;
mp[a].push_back(b);
nx[b] += 1;
}
priority_queue<int> q;
for (int i = 1; i <= n; i++) {
if (nx[i] == 0) {
q.push(-i);
visited[i] = true;
}
}
while (!q.empty()) {
int cur = -q.top(); q.pop();
res.push_back(cur);
for (int i = 0; i < mp[cur].size(); i++) {
int nxt = mp[cur][i];
nx[nxt] -= 1;
if (!visited[nxt] && nx[nxt] == 0) {
visited[nxt] = true;
q.push(-nxt);
}
}
}
for (int i = 0; i < n; i++) {
cout << res[i] << ' ';
}
cout << endl;
return 0;
}
