BOJ 2252 - 줄 세우기

문제

• \(N(1 \le N \le 32000),\; M(1\le M \le 100000)\)이 주어진다.
• \(N\)개의 정점에 대해 \(M\) 개의 단방향 간선이 주어질 때, 위상 정렬의 경우의 수 중 하나를 출력해야 한다.

풀이

• In-degree, DFS를 사용하는 방법을 모두 구현해서 실행 시간을 비교해보았다.

In-degree

1. ind[n] 배열에 각 정점의 in-degree 정보를 저장한다.
2. ind[i]==0인 i들을 큐 q에 추가한다.
3. !q.empty()일 동안 아래 과정을 반복한다.
   1. q에서 v=dequeue()하며 front였던 정점 v를 res 리스트에 추가한다.
   2. v에 대해 v x 관계인 x의 ind[x]를 1씩 감소한다.
      이떄 ind[x]가 0이되면 enqueue(x)를 실행한다.
4. res가 위상 정렬 결과이다.

In-degree 코드

#include <iostream>
#include <queue>
#include <vector>
#define v vector

using namespace std;
using vi = vector<int>;

// in-degree
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vi ind(n, 0), ans;
    v<vi> adj(n, vi(0));
    queue<int> q;
    for (int i = 0; i < m; i++) {
        int s, e;
        cin >> s >> e;
        s--, e--;
        adj[s].push_back(e);
        ind[e]++;
    }
    for (int i = 0; i < n; i++) {
        if (ind[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        ans.push_back(cur + 1);
        for (int i = 0; i < adj[cur].size(); i++) {
            int nv = adj[cur][i];
            ind[nv]--;
            if (ind[nv] == 0) {
                q.push(nv);
            }
        }
    }
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << ' ';
    }
    return 0;
}

DFS

1. vis[n]에 정점의 방문 여부를 저장한다.
2. vis[i]==0인 정점 i에 대해 아래 과정의 DFS(i)를 실행한다.
   1. vis[i]=1
   2. i x 관계에 대해 vis[x]==0이면 DFS(x) 실행
   3. res 리스트의 첫 부분에 i 추가
3. res가 위상 정렬 결과이다.

DFS 코드

#include <algorithm>
#include <iostream>
#include <vector>
#define v vector

using namespace std;
using vi = vector<int>;

// DFS
int tpsort(v<vi> &adj, vi &vis, int v, vi &tv) {
    vis[v] = 1;
    for (int i = 0; i < adj[v].size(); i++) {
        int nv = adj[v][i];
        if (vis[nv] == 0)
            tpsort(adj, vis, nv, tv);
    }
    tv.push_back(v);
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;
    cin >> n >> m;
    vi vis(n, 0), ans;
    v<vi> adj(n, vi(0));
    for (int i = 0; i < m; i++) {
        int t1, t2;
        cin >> t1 >> t2;
        adj[t1 - 1].push_back(t2 - 1);
    }
    for (int i = 0; i < n; i++) {
        if (vis[i] == 0) {
            tpsort(adj, vis, i, ans);
        }
    }
    reverse(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++)
        cout << ans[i] + 1 << ' ';
    return 0;
}

풀고나서

• 두 방법에 대한 채점 결과는 아래 표와 같다.

방법	메모리	시간
In-degree	4220KB	24ms
DFS	4216KB	28ms

• 메모리 차이는 크게 없지만, In-degree가 실행 속도가 미세하게 더 빠르다.
  • DFS의 재귀 호출의 영향이라 짐작된다.