[BOJ 32674 // C++] Palindromic Word Search

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

 

이번에 볼 문제는 백준 32674번 문제인 Palindromic Word Search이다.
문제는 아래 링크를 확인하자.

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

 

직사각형 영역의 임의의 행과 열을 하나씩 고르면 고른 행과 열에 공통으로 속한 칸이 항상 존재한다. (좌표의 원리를 생각하자.) 따라서, 임의의 직사각형 영역에 문제의 조건을 만족하는 행방향의 팰린드롬과 열방향의 팰린드롬이 하나씩 있다면 그 둘을 모두 포함하는 어떤 칸이 항상 존재한다.

 

따라서 이 문제는 각 칸을 지나는 행방향 팰린드롬의 길이의 최댓값과 열방향 팰린드롬의 길이의 최댓값을 모두 구해 각 칸을 교점으로 하는 직사각형의 넓이의 최댓값을 구하는 것으로 해결할 수 있다.

 

하나의 행 또는 열에 대하여, 각 문자(또는 두 문자 사이)를 중심으로 하는 팰린드롬의 길이의 최댓값은 manacher 알고리즘 등을 이용해 빠르게 구할 수 있고, sweeping을 통해 각 행 또는 열의 칸에 대하여 그 칸을 포함하는 해당 방향 팰린드롬의 길이의 최댓값을 구해낼 수 있다.

 

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

// 찾는 사각형은 공통된 칸이 있고,
// 해당 칸 포함 가로 팰린드롬 최대 길이와 세로 팰린드롬 최대 길이를 각각 전처리해서
// 모든 칸에 대해 계산 시도
#include <iostream>
#include <queue>
using namespace std;

int R, C, ans;
char board[500][500];
int valR[500][500], valC[500][500];
string s;
int dp[1001];

void manacher(string& S) {
	int N = S.length();
	priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<>> pq1;
	pq1.push(make_pair(make_pair(0, 0), 0));
	dp[0] = 0;
	for (int c = 0, i = 1; i < N; i++) {
		if (i <= c + dp[c]) dp[i] = min(dp[c - (i - c)], (c + dp[c]) - i);
		else dp[i] = 0;
		while (-1 < i - dp[i] - 1 && i + dp[i] + 1 < N && S[i - dp[i] - 1] == S[i + dp[i] + 1]) dp[i]++;
		if (c + dp[c] < i + dp[i]) c = i;
		pq1.push(make_pair(make_pair(i - dp[i], i + dp[i]), dp[i]));
	}
	priority_queue<pair<int, int>> pq2;
	for (int i = 0; i < N; i++) {
		while (!pq1.empty() && pq1.top().first.first == i) {
			pq2.push(make_pair(pq1.top().second, pq1.top().first.second));
			pq1.pop();
		}
		while (pq2.top().second < i) pq2.pop();
		dp[i] = pq2.top().first;
	}
}

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

	s.reserve(1001);
	cin >> R >> C;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> board[r][c];
		}
	}

	for (int r = 0; r < R; r++) {
		s.clear();
		s += '#';
		for (int c = 0; c < C; c++) {
			s += board[r][c];
			s += '#';
		}
		manacher(s);
		for (int c = 0; c < C; c++) valR[r][c] = dp[c * 2 + 1];
	}

	for (int c = 0; c < C; c++) {
		s.clear();
		s += '#';
		for (int r = 0; r < R; r++) {
			s += board[r][c];
			s += '#';
		}
		manacher(s);
		for (int r = 0; r < R; r++) valC[r][c] = dp[r * 2 + 1];
	}

	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			ans = max(ans, valR[r][c] * valC[r][c]);
		}
	}

	cout << ans;
}