[BOJ] 백준 2529 부등호

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

Approach

DFS (depth-first search, 깊이 우선 탐색)

깊이 우선 탐색(depth-first search, DFS)

DFS와 BFS 비교  

DFS와 BFS 비교

---

#include <stdio.h>
typedef long long LL;
LL ansMax, ansMin = (LL)99e8;
int N, info[11], permut[11];
int used[11];

void DFS(int lev) {
    if (lev > N) {
        LL d = 0;
        for (int i = 0; i <= N; ++i)
            d = d * 10 + permut[i];
        if (d > ansMax) ansMax = d;
        if (d < ansMin) ansMin = d;
        return;
    }

    for (int i = 0; i < 10; ++i) if (!used[i]) {
        permut[lev] = i;
        if (lev) {
            if (info[lev] && permut[lev - 1] > permut[lev]) continue;
            if (!info[lev] && permut[lev - 1] < permut[lev]) return;
        }
        used[i] = 1;
        DFS(lev + 1);
        used[i] = 0;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d", &N);

    char cmd;
    for (int i = 1; i <= N; ++i) {
        scanf(" %c", &cmd);
        info[i] = cmd == '<';
    }

    DFS(0);

    printf("%0*lld\n", N + 1, ansMax);
    printf("%0*lld\n", N + 1, ansMin);
}