[백준 BOJ][C++]2529번 부등호 풀이: DFS

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

2529번: 부등호

 

 이 문제는 DFS로 해결할 수 있습니다. 

 

 최대, 최소 정수 두 가지만 뽑으면 되기 때문에, 최대 정수를 찾는 dfs, 최소 정수를 찾는 dfs 두 함수를 작성하여 빠르게 두 정수를 찾을 수 있습니다 .

 

 때문에 문자열의 길이가 k라면 최대, 최소 정수를 찾은 것이므로 그 즉시 dfs를 종료합니다. 

 

 

[풀이 과정]

1. 괄호 정보를 저장하는 comp 배열에 괄호 입력

2. 9부터 max_dfs() 

3. 괄호에 맞게 비교

4. 아직 방문하지 않은 수에 대해 조건이 충족하다면 문자열에 해당 숫자를 추가하고 dfs 재귀 호출

5. 만약 depth가 k라면 최대 정수를 찾은 것이므로 그 즉시 dfs 종료

6. 최소 정수도 0부터 시작하여 min_dfs() 실행

 

 

#include<iostream>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<string>
#include<algorithm>

using namespace std;

typedef pair<int, int> tp;

int k;
char comp[10];
bool visit[10] = { false, };
bool max_flag = false;
bool min_flag = false;
string max_str;
string min_str;

void max_dfs(int num, string str, int depth) {

	if (max_flag)
		return;

	if (depth == k) {
		max_flag = true;
		max_str = str;
		return;
	}

	char c = comp[depth];

	if (c == '<') {
		for (int i = 9; i >= 0; i--) {
			if (max_flag)
				break;
			if (num < i && !visit[i]) {
				visit[i] = true;
				max_dfs(i, str + to_string(i), depth + 1);
				visit[i] = false;
			}
		}
	}
	else if (c == '>') {
		for (int i = 9; i >= 0; i--) {
			if (max_flag)
				break;
			if (num > i && !visit[i]) {
				visit[i] = true;
				max_dfs(i, str + to_string(i), depth + 1);
				visit[i] = false;
			}
		}
	}
}

void min_dfs(int num, string str, int depth) {

	if (min_flag)
		return;

	if (depth == k) {
		min_flag = true;
		min_str = str;
		return;
	}

	char c = comp[depth];

	if (c == '<') {
		for (int i = 0; i <= 9; i++) {
			if (min_flag)
				break;
			if (num < i && !visit[i]) {
				visit[i] = true;
				min_dfs(i, str + to_string(i), depth + 1);
				visit[i] = false;
			}
		}
	}
	else if (c == '>') {
		for (int i = 0; i <= 9; i++) {
			if (min_flag)
				break;
			if (num > i && !visit[i]) {
				visit[i] = true;
				min_dfs(i, str + to_string(i), depth + 1);
				visit[i] = false;
			}
		}
	}
}

int main(void) {

	cin >> k;

	for (int i = 0; i < k; i++)
		cin >> comp[i];

	for (int i = 9; i >= 0; i--) {
		visit[i] = true;
		max_dfs(i, to_string(i), 0);
		visit[i] = false;
	}

	memset(visit, false, sizeof(visit));

	for (int i = 0; i <= 9; i++) {
		visit[i] = true;
		min_dfs(i, to_string(i), 0);
		visit[i] = false;
	}


	cout << max_str << endl;
	cout << min_str << endl;

	return 0;
}