BOJ 1509: 팰린드롬 분할

 

 

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

1509번: 팰린드롬 분할

문제를 간단히 요약하자면 주어진 문자열을 부분 문자열들로 나누는데 모든 부분 문자열이 팰린드롬이어야 한다. 이때 부분 문자열의 최소 개수를 구하는 문제이다.

 

가장 처음 시도한 방법은 모든 구간 $[l, r]$에 대하여 팰린드롬인가를 확인할 수 있는 배열 $chk[l][r]$을 만들었다. 이후 행렬 곱셈 순서 문제와 비슷한 아이디어로 문자열이 두 개의 부분 문자열로 나누어질 때에 대해 생각해봤다.

즉 $[l, i]$와 $[i + 1, r]$ (단, $l \leq i < r$)이 팰린드롬인지 확인하고 팰린드롬이라면 1을 더해주고, 팰린드롬이 아니라면 넘어가는 방법을 이용했다.

구현하면서 꽤 괜찮은 아이디어라고 생각을 하고 제출해봤지만 TLE를 받았다.

TLE를 받은 후 두 부분 문자열 $S_{l...i}$와 $s_{i+1...r}$ 중 적어도 하나가 팰린드롬인 경우만으로 조건을 약간 바꿔봤지만 역시나 길이 2500의 랜덤 문자열을 판단하는데에는 제법 오랜 시간이 걸렸다.

실제로 이 방법은 모든 구간$[l, r]$에 대해 $d[l][r]$을 구해야하고, 각각의 답을 구하기 위해 $r - l$번 연산을 하기 때문에 $O(n^3)$에 문제를 해결하기 때문에 TLE를 받을 수 밖에 없다.

그렇다면 조금 더 효율적으로 답을 구하는 방법에 대해 고민해볼 필요가 있다.

 

사실 반쯤 감긴 눈으로 의자에 앉아 고민을 하다보니 번뜩이는 아이디어가 떠올랐다. 결론부터 얘기하자면 BFS를 이용하는 방법이다.

먼저 chk배열을 통해 모든 구간 $[l, r]$에 대하여 팰린드롬인가를 확인하는 것은 동일하다. 하지만 이 preprocess 과정에서 하나의 작업을 더 해준다. 인접 리스트를 만들어 node $l$과 node $r + 1$이 연결된 방향 그래프를 만들어 주는 것이다. 특정 구간이 팰린드롬이라면 해당 구간을 부분 문자열로 떼어낼 수 있으므로 간선의 가중치는 1이다. 이렇게 만들어준 인접 리스트를 이용하여 시작 node인 0번 node부터 마지막 노드인 $|S|$까지 BFS를 이용하여 최단 거리를 구해준다면 문제의 조건을 만족하는 정답을 구할 수 있다.
사실 MLE가 나지 않을까 내심 걱정했지만 의외로 통과했다. 

#include<bits/stdc++.h>
using namespace std;
int chk[2525][2525];
vector<int> adj[2525];
char msg[2525];
int d[2525];
bool pal(int l, int r) {
	if (l >= r) return 1;
	int& res = chk[l][r];
	if (~res) return res;
	res = 0;
	res = pal(l + 1, r - 1) && msg[l] == msg[r];
	if (res)
		adj[l].push_back(r + 1);

	pal(l + 1, r);
	pal(l, r - 1);
	return res;
}
int main() {
	memset(chk, -1, sizeof(chk));
	scanf("%s", msg);
	int sz = 0;
	for (; msg[sz]; ++sz) {
		chk[sz][sz] = 1;
		adj[sz].push_back(sz + 1);
	}
	pal(0, sz - 1);
	queue<int> q;
	q.push(0);
	d[0] = 1;
	while (q.size()) {
		int cur = q.front(); q.pop();
		if (cur == sz) {
			printf("%d", d[cur] - 1);
			return 0;
		}
		for (int i = 0; i < adj[cur].size(); ++i) {
			int nx = adj[cur][i];
			if (d[nx] == 0) {
				d[nx] = d[cur] + 1;
				q.push(nx);
			}
		}
	}
}

Preprocess를 단순한 방법이 아닌 부분 문자열이 팰린드롬인지 $O(n)$에 확인할 수 있는 Manacher's Algorithm을 이용한다면 조금 더 실행속도를 빠르게 만들 수 있으리라 생각한다. 하지만 잘 모르는 알고리즘이기에 나중에 공부해서 다시 풀어볼까 생각중이다.

문제의 알고리즘 분류가 dp로 되어있는데 사실 dp로는 어떻게 접근해야 할 지 잘 모르겠다.