[알고리즘] 백준 6443번: 애너그램 (C++), 백트래킹 중복 처리 유형 2번째!

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

6443번: 애너그램

단순한 백트래킹 문제인 줄 알았으나 꽤 조건이 까다로운 문제다.

허나, 이 조건은 예전에 N과 M 시리즈를 풀 때도 한 번 크게 겪었던 똑같은 유형이었다.

(N과 M (9) 문제: https://www.acmicpc.net/problem/15663)

(N과 M (9) 포스팅: https://draw-code-boy.tistory.com/29)

 

이 문제에서 필요한 건 정렬과 이전 노드(같은 depth)에 대한 기억

정렬이 필요한 이유는 예를 들어 acba라는 문자열이 주어졌을 때의 애너그램을 구한다고 하면

정렬이 되지 않으면 처음에 등장하는 a라는 노드에 대한 기억을 c로 넘어가면서 지워져 버리기 때문이다.

>> 정렬을 통해 같은 노드끼리 묶어두려는 방법이다.

 

예전에는 이 문제를 이해하느라 엄청 어려웠었는데 쉽게 이해할 수 있는 방법(?)을 찾은 거 같다.

백트래킹을 통해 발생하는 재귀의 횟수를 depth라고 했을 때, 같은 depth에 같은 노드가 있다는 건 똑같은 문자열이 구해진다는 것과 같다.

그래서 아래에 before이라는 기억을 하는 변수는 모두 같은 depth에 해당이 되는 노드들 간에 관계성을 구하는 변수이다.

 

void backTrack(string value, int cnt, string ret) {
	if (cnt == value.size()) {
		cout << ret << '\n';
		return;
	}

	char before = '!';
	for (int i = 0; i < value.size(); i++) {
		if (!visited[i] && value[i] != before) {
			visited[i] = 1;
			before = value[i];
			backTrack(value, cnt + 1, ret + value[i]);
			visited[i] = 0;
		}
	}
}

 

N과 M (9)를 안 풀어본 사람들이 이 문제가 어렵다고 느껴질 수 있는 이유는 기존의 백트래킹에서는 항상 재귀의 조건(세로)만 따졌다면 이 문제에서는 같은 depth의 노드들끼리의 관계(가로)도 신경 써야 하기 때문이다.

(가로와 세로는 그저 이해를 돕기 위한 말)

(물론 재귀의 조건에서 가로도 따진다.)

---

[AC 코드]

#include <iostream>
#include <algorithm>
using namespace std;

int T;
bool visited[20] = { 0, };

void backTrack(string value, int cnt, string ret) {
	if (cnt == value.size()) {
		cout << ret << '\n';
		return;
	}

	char before = '!';
	for (int i = 0; i < value.size(); i++) {
		if (!visited[i] && value[i] != before) {
			visited[i] = 1;
			before = value[i];
			backTrack(value, cnt + 1, ret + value[i]);
			visited[i] = 0;
		}
	}
}

int main() {
	cin >> T;
	for (int t = 0; t < T; t++) {
		string value;
		cin >> value;
		sort(value.begin(), value.end());
		string ret = "";
		backTrack(value, 0, ret);
	}

	return 0;
}

---

공부한 거 써먹었다 ㅎㅎ