취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 6913번 문제인 Constrained Permutation이다.
문제는 아래 링크를 확인하자.

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

주어지는 나열 순서를 모두 만족하는 순열의 개수를 구하는 문제이다.

글쓴이는 위상정렬과 같은 원리로 앞서 와야 하는 수가 모두 등장한 경우에만 해당 수를 순열에 등장시키는 방식으로 문제를 해결하였다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;

int N, K;
int deg[10];
vector<int> G[10];
bool visited[10];
int ans;
vector<int> vec;
void src(int cur, int lv) {
    if (lv == N) {
        ans++;
        return;
    }
    for (auto &x:G[cur]) {
        deg[x]--;
        if (!deg[x]) vec.emplace_back(x);
    }
    for (auto &nxt:vec) {
        if (!visited[nxt]) visited[nxt] = 1, src(nxt, lv + 1), visited[nxt] = 0;
    }
    for (auto &x:G[cur]) {
        if (!deg[x]) vec.pop_back();
        deg[x]++;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    vec.reserve(10);
    cin >> N >> K;
    while (K--) {
        int x, y; cin >> x >> y;
        G[x].emplace_back(y), deg[y]++;
    }
    
    for (int i = 1; i <= N; i++) {
        if (!deg[i]) vec.emplace_back(i);
    }
    src(0, 0);
    cout << ans;
}