[BOJ 24891 // C++] 단어 마방진

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 24891번 문제인 단어 마방진이다.
문제는 아래 링크를 확인하자.

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

24891번: 단어 마방진

N개의 단어중 L개의 단어를 나열하는 각 경우를 사전순으로 접근해보자. 이를 위해 주어진 N개의 단어들을 정렬할 필요가 있다.

 

L개의 단어들을 순서대로 배열했을 때 단어 마방진이 된다면 아직 단어 마방진을 출력하지 않았다면 해당 마방진을 출력하고 이후에 나올 마방진은 출력하지 않게끔 구현하자.

 

어떠한 단어 마방진도 출력하지 못했다면 "NONE"을 출력하자.

 

아래는 제출한 소스코드이다.

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

string arr[20];
string ans[5];
bool visited[20];
int L, N;
bool chk = 0; // 0: 답 출력 안함, 1: 답 출력함

void func(int cnt) {
	if (cnt == L) {
		if (!chk) {
			bool sign = 1;
			for (int i = 0; i < L; i++) {
				for (int j = i + 1; j < L; j++) {
					if (ans[i][j] != ans[j][i]) sign = 0;
				}
			}
			if (sign) {
				chk = 1;
				for (int i = 0; i < L; i++) cout << ans[i] << '\n';
			}
		}
	}
	else {
		for (int i = 0; i < N; i++) {
			if (visited[i]) continue;
			visited[i] = 1;
			ans[cnt] = arr[i];
			func(cnt + 1);
			visited[i] = 0;
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> L >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	sort(arr, arr + N);

	func(0);

	if (!chk) cout << "NONE";
}