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

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

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