[BOJ 24891] 백준 24891번 - 단어 마방진

March 28, 2022

		2022 숭고한 연합 알고리즘 콘테스트 Open Contest 풀이
A		[BOJ 24883] 자동완성
B		[BOJ 24884] 장작 넣기
C		[BOJ 24885] 주식
D		[BOJ 24886] SKH 문자열
E		[BOJ 24887] 최대한의 휴식
F		[BOJ 24888] 노트 조각
I		[BOJ 24891] 단어 마방진

1. 문제Permalink

$24891$ . 단어 마방진 (2022 숭고한 연합 알고리즘 콘테스트 I번)

백준 24891번 - 단어 마방진 (https://www.acmicpc.net/problem/24891)

2. 풀이Permalink

$L\leq 5,\, N\leq 20$ 이다. 따라서 $20$ 개 중 $5$ 개를 고르는 작업이므로, $_{20}C_5=15,504$ 가지 경우의 수가 있다. 그런데 코드 상으로는 $1$ 부터 $20$ 까지 전체를 탐색하므로, $20^5=3,200,000$ 로 보아야 한다. 어찌됐든 브루트포스로 충분히 탐색이 가능하다.

$L$ 개의 단어를 고르고 이를 마방진으로 배치한 뒤, 단어 마방진의 조건을 만족하는지 확인하기만 하면 된다. 단, 사전 순으로 가장 빠른 단어 마방진을 출력해야 하므로, 처음에 단어들을 정렬한 뒤에 탐색을 시작한다.

3. 채점 결과Permalink

boj-24891

4. 회고Permalink

정해진 단어들을 바탕으로 가능한 단어들을 추려내어 시간복잡도를 줄일 수도 있겠다고 생각했지만, 완전탐색이 가능하여 굳이 시도하진 않았던 문제였다.

5. 코드Permalink

	#include <bits/stdc++.h>
	using namespace std;

	#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
	#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
	#define ll long long int
	#define pii pair<int, int>
	#define PQ priority_queue
	#define LEN(v) int(v.size())
	#define ALL(v) v.begin(),v.end()
	#define INF 2e9
	#define LINF 1e18

	int L, N;
	vector<string> v(20);
	vector<bool> visited(20, 0);
	vector<string> ans(20);

	void DFS(int cnt) {
	if (cnt == L) {
	bool flag = true;
	FOR(i, 0, L - 1) {
	FOR(j, i + 1, L - 1) {
	flag &= (ans[i][j] == ans[j][i]);
	}
	}
	if (flag) {
	FOR(i, 0, L - 1) {
	FOR(j, 0, L - 1) {
	cout << ans[i][j];
	}
	cout << "\n";
	}
	exit(0);
	}
	return;
	}
	FOR(i, 0, N - 1) {
	if (visited[i]) continue;
	visited[i] = 1;
	ans[cnt] = v[i];
	DFS(cnt + 1);
	visited[i] = 0;
	}
	}

	int main() {
	FASTIO;
	cin >> L >> N;
	FOR(i, 0, N - 1) {
	cin >> v[i];
	}
	sort(v.begin(), v.begin() + N);
	DFS(0);
	cout << "NONE";

	return 0;
	}

view raw [BOJ 24891] 단어 마방진.cpp hosted with ❤ by GitHub

Twitter Facebook LinkedIn

이성주