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

백트래킹을 이용한 풀이는

코드가 직관적이므로 별도로 설명하진 않겠습니다.

백트래킹 코드

#include <bits/stdc++.h>
using namespace std;

int n;
char arr[20];
bool ch[10];
int path[20];

long long minn = LLONG_MAX, maxx = LLONG_MIN;

void DFS(int L) {
    if (L == n + 1) {
        for (int i = 1; i <= n; i++) {
            if (arr[i] == '<') {
                if (path[i - 1] > path[i]) {
                    return;
                }
            }
            else {
                if (path[i - 1] < path[i]) {
                    return;
                }

            }
        }


        long long x = 0;

		for (int i = 0; i < L; i++) {
			x = x * 10 + path[i];
		}

        minn = min(minn, x);
        maxx = max(maxx, x);

    }
    else {
        for (int i = 0; i <= 9; i++) {
            if (ch[i] == 0) {
				ch[i] = 1;
				path[L] = i;
				DFS(L + 1);
				ch[i] = 0;
			}
        }
    }
}


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

    cin >> n;

    long long comp = pow(10, n);

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }


    DFS(0);

    cout << maxx << '\n';

    if (minn < comp) {
        cout << 0;
    }

    cout << minn << '\n';



    return 0;
}

백준 2529 부등호 위상정렬로 푸는 법

위상정렬을 공부하다 다른 블로그의 설명을 많이 봤는데 이해가 잘 되지 않았어서

한참 헤맸습니다.

노드 번호와 해당 노드의 숫자를 별개로 생각해야합니다.

A노드와 B 노드가 있다고 가정합니다.

부등호를 기준으로

A > B 라면 A -> B 를 향하는 간선을 주고

위상정렬을 수행합니다.

예제에서 먼저 최댓값을 생각해보면

2
< >

A < B > C 이면

B -> A

B -> C 가 간선이 되고

위상정렬을 수행하면 순서가

B A C 이거나

B C A 가 됩니다.

이 뜻은 B가 가장 커야하고 A와 C는 따로 정해주어야 한다는 뜻입니다.

그래서 B는 9가 되고 A C 가 8 7이 되어야 하는데

최댓값을 구할 때 먼저 나온게 커야하므로 A에 8을 주고 C에 7을주면

B : 9 ,

A : 8,

C : 7,

이 되고 원래 숫자는 ABC 순서이므로

897이 최대가 됩니다.

최솟값을 구할 땐

가장 큰 수인 B에 숫자를 넣을 때 9부터 넣는게 아닌 K(2)부터 넣어야 최솟값이 구해집니다.

그리고 A 와 C를 정할 때 앞에 있는 숫자가 작은 숫자여야 최솟값이 되므로 A에 0 C에 1을 넣으면 됩니다.

그러면

B : 2

A : 0

C : 1

이므로 정답은 ABC 021이 됩니다.

간선 정보는 동일하게 이용하고 degree(차수)를 줄여주면서 큐를 돌 때

노드번호를 각각 최소힙, 최대힙으로 주면서 뽑아주면서

노드에 숫자를 하나씩 넣으면 됩니다.

위상정렬 코드

#include <bits/stdc++.h>
using namespace std;

int k;
char arr[20];

int node[11]; // 최댓값 구하는데 사용
int degree[11]; 
int node2[11]; // 최솟값 구하는데 사용
int degree2[11]; 
bool ch[11][11];


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

    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> arr[i];

        if (arr[i] == '<') {
            ch[i + 1][i] = 1;
            degree[i]++;
            degree2[i]++;
        }
        else{
            ch[i][i + 1] = 1;
            degree[i + 1]++;
            degree2[i + 1]++;
        }
    }

    priority_queue<int> Q;

    //최댓값 구하기 

    for (int i = 1; i <= k + 1; i++) {
        if (degree[i] == 0) {
            Q.push(-i);
        }
    }

    int cnt = 9;
    while (!Q.empty()) {
        int x = -Q.top();
        Q.pop();
        node[x] = cnt--;
        for (int i = 1; i <= k + 1; i++) {
            if (ch[x][i] == 1) {
                if (--degree[i] == 0) {
                    Q.push(-i);
                }
            }
        }
    }

    for (int i = 1; i <= k + 1; i++) {
        cout << node[i];
    }
    cout << '\n';





    //최솟값 구하기

    for (int i = 1; i <= k + 1; i++) {
        if (degree2[i] == 0) {
            Q.push(i);
        }
    }

    cnt = k;
    while (!Q.empty()) {
        int x = Q.top();
        Q.pop();
        node2[x] = cnt--;
        for (int i = 1; i <= k + 1; i++) {
            if (ch[x][i] == 1) {
                if (--degree2[i] == 0) {
                    Q.push(i);
                }
            }
        }
    }

    for (int i = 1; i <= k + 1; i++) {
        cout << node2[i];
    }
    cout << '\n';


   
    return 0;
}

위상정렬을 이용했을 때 시간은 0ms

백트래킹을 이용했을 때 120ms

백트래킹에서 가지치기를 하진 않았지만, 위상정렬을 이용할 때

더 빠른 시간 내에 문제를 해결 할 수 있습니다.

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

1. 문제설명

단방향 그래프 관계가 주어지고

그래프에서 간선의 방향을 수정했을 때

위상정렬을 수행하면 단 하나의 경우의 수만 나오는지 확인하는 문제다.

2. 접근방법[알고리즘]

우선 위상정렬을 수행하는데 확인해야 할 게 두가지 있다.

첫 번째는

단 하나의 경우의 수만 등장하는지 ==

확실한 순위를 찾을 수 있는지 확인해야한다.

이를 확인하려면 위상정렬을 하면서 큐의 size를 확인해야 한다.

만약 하나의 노드에서 여러 노드로 퍼질 수 있다면

큐의 사이즈가 2를 넘게 되고 이때는 위상정렬의 가짓 수가 여러개가 되어서 확실한 순위를 찾을 수 없다.

두번째는 

사이클이 존재하다면 IMPOSSIBLE을 출력해야한다.

사이클이 존재하면 위상정렬이 불가능하고,

그 경우에 위상정렬 과정에서 degree(차수) 가 0이 되지 않는 노드가 생기기 때문에

모든 노드를 탐색하지 못한다.

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

bool adj[501][501];
int degree[501];


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t;
    cin >> t;
    for (int T = 0; T < t; T++) {

        memset(adj, 0, sizeof(adj));
        memset(degree, 0, sizeof(degree));
        int n;
        cin >> n;

        vector<int> pre;
        for (int i = 0; i < n; i++) {
            int tmp;
            cin >> tmp;
            pre.push_back(tmp);
        }

		for (int i = 0; i < pre.size(); i++) {
            for (int j = i + 1; j < pre.size(); j++) {
                adj[pre[i]][pre[j]] = 1;
                degree[pre[j]]++;
            }
        }

        int m;
        cin >> m;


        for (int i = 0; i < m; i++) {
            int a, b;
            cin >> a >> b;

            if (adj[a][b] == 1) {
                adj[a][b] = 0;
                degree[b]--;
                adj[b][a] = 1;
                degree[a]++;
            }
            else {
                degree[a]--;
                adj[b][a] = 0;
                adj[a][b] = 1;
                degree[b]++;
            }
        }

        
        queue<int> Q;

        for (int i = 1; i <= n; i++) {
            if (degree[i] == 0) {
                Q.push(i);
            }
        }

        vector<int> ans;

        bool cantKnow = false;

        while (!Q.empty()) {

            if (Q.size() >= 2) {
                cantKnow = true;
                break;
            }

            int x = Q.front(); Q.pop();
            ans.push_back(x);

            for (int i = 1; i <= n; i++) {
                if (adj[x][i] == 1) {
                    int nx = i;

                    if (--degree[nx] == 0) {
                        Q.push(nx);
                    }

                }
            }
        }

        if (cantKnow) {
            cout << "?\n";
            continue;
        }


        if (ans.size()!=n) {
            cout << "IMPOSSIBLE\n";
            continue;
        }
        else {
			for (auto x : ans) {
				cout << x << ' ';
			}
			cout << '\n';
        }


    }
  
    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int d[1001];
vector<int> adj[1001];
int degree[1001];
int res[1001];

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

    for (int T = 0; T < t; T++) {
        int n, k;
        cin >> n >> k;
        memset(degree, 0, sizeof(degree));
        memset(res, 0, sizeof(res));
        memset(d, 0, sizeof(d));
        for (int i = 0; i < 1001; i++) adj[i].clear();


        for (int i = 1; i <= n; i++) {
            cin >> d[i];
        }

        for (int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            degree[b]++;
        }
        int w;
        cin >> w;

        queue<int> Q;

        for (int i = 1; i <= n; i++) {
            if (degree[i] == 0) {
                Q.push(i);
                res[i] = d[i];
            }
        }

        while (!Q.empty()) {
            int x = Q.front(); Q.pop();

            for (auto nx : adj[x]) {
                res[nx] = max(res[nx], res[x] + d[nx]);
                if (--degree[nx] == 0) {
                    Q.push(nx);
                }
            }

        }


        cout << res[w] << '\n';



    }


    return 0;
}

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

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> adj[32001];
int degree[32001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;

        adj[a].push_back(b);
        degree[b]++;
    }

    priority_queue<int> Q;

    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            Q.push(-i);
        }
    }
    vector<int> ans;

    while (!Q.empty()) {
        int x = -Q.top();
        Q.pop();
        ans.push_back(x);

        for (auto nx : adj[x]) {
            if (--degree[nx] == 0) {
                Q.push(-nx);
            }
        }
    }

    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << ' ';
    }
    

    return 0;
}

우선순위 큐를 활용한 위상정렬 문제

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

위상정렬을 수행하는데 사이클이 존재하면

계속해서 degree가 0이 되지 않기 때문에

#include <bits/stdc++.h>

using namespace std;

int n, m;
int degree[1001];
vector<int> adj[1001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
   
    cin >> n >> m;
    // 그래프 만들기 
    for (int i = 0; i < m; i++) {
        int tmp;
        cin >> tmp;

		int pre = -1;
        for (int j = 0; j < tmp; j++) {
            int now;
            cin >> now;
            if (pre != -1) {
                adj[pre].push_back(now);
                degree[now]++;
            }
            pre = now;
        }
    }

    vector<int> order;
    queue<int> Q;
    for (int i = 1; i <= n; i++) {
        if (degree[i] == 0) {
            Q.push(i);
        }
    }

    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        order.push_back(x);


        for (auto nx : adj[x]) {
            if (degree[nx] > 0) {
				degree[nx]--;
                if (degree[nx] == 0) {
                    Q.push(nx);
                }
            }
        }
    }

    if (order.size() == n) {
        for (auto x : order) {
            cout << x << '\n';
        }
    }
    else {
        cout << 0 << '\n';
    }




    return 0;
}