(백준 10597번 순열장난 C++) 라이님 블로그 대회 알고리즘 따라잡기 10) Backtracking 2

강제종료로 해결해버린 문제!ㅋㅋㅋㅋ

 

백준 10597번

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

10597번: 순열장난

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

string st;
int stsize, M;
bool visited[51] = { false };
vector<int> v;

void dfs(int curr) {
	if (curr == stsize) {
		int mul = 1;
		for (int i = 1; i <= M; i++) mul = mul * visited[i];
		if (mul == 0) return;
		for (int x : v) cout << x << ' ';
		exit(0);
	}
	if (curr == stsize - 1) {
		v.push_back(st[curr] - '0');
		visited[st[curr] - '0'] = true;
		dfs(curr + 1);
		return;
	}

	int num = (st[curr] - '0') * 10 + (st[curr + 1] - '0');
	if (visited[num] == false && num < M + 1) {
		visited[num] = true;
		v.push_back(num);
		dfs(curr + 2);
		v.pop_back();
		visited[num] = false;
	}
	num = st[curr] - '0';
	if (visited[num] == false && num < M + 1) {
		visited[num] = true;
		v.push_back(num);
		dfs(curr + 1);
		v.pop_back();
		visited[num] = false;
	}
}

int main() {
	cin >> st;
	stsize = st.size();
	if (stsize < 10) M = stsize;
	else M = 9 + (stsize - 9) / 2;
	dfs(0);
	return 0;
}

 

 

exit(0)로 하나의 case만 출력할 수 있도록 만들어보았다. 그닥 바람직한 방법은 아닌거 같은데..

 

코드가 겹치는 부분이 많아서 chatgpt한테 단순화해달라고 부탁했더니 아래와 같이 단순화해주었다.

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

string st;
int stSize, M;
bool visited[51] = { false };
vector<int> v;

bool dfs(int curr) {
    if (curr == stSize) {
        for (int i = 1; i <= M; i++) {
            if (!visited[i]) return false;
        }
        for (int x : v) cout << x << ' ';
        cout << '\n';
        return true;
    }

    // 한 자리 숫자 처리
    int num = st[curr] - '0';
    if (!visited[num] && num <= M) {
        visited[num] = true;
        v.push_back(num);
        if (dfs(curr + 1)) return true;
        v.pop_back();
        visited[num] = false;
    }

    // 두 자리 숫자 처리 (현재 위치에서 다음 숫자까지 포함하여 두 자리 수 생성 가능한지 확인)
    if (curr + 1 < stSize) {
        num = num * 10 + (st[curr + 1] - '0');
        if (!visited[num] && num <= M) {
            visited[num] = true;
            v.push_back(num);
            if (dfs(curr + 2)) return true;
            v.pop_back();
            visited[num] = false;
        }
    }
    return false;
}

int main() {
    cin >> st;
    stSize = st.size();
    M = stSize < 10 ? stSize : 9 + (stSize - 9) / 2;
    dfs(0);
    return 0;
}

 

여기서 눈여겨봐야 할 것은 dfs의 반환형이 bool이라는 점!

이렇게 하면 exit을 사용하지 않고도 가능한 하나의 경우에 대해서만 출력할 수 있다!

 

처음에는 이해가 잘 되지는 않았는데..

함수가 true를 반환하면 그 함수를 호출한 상위함수는 이 반환 값을 받게 된다. 이 경우 상위함수도 추가적인 처리 없이 true를 반환하고 종료할 수 있다.

 

이 문장을 보고 이해했다!!!