취미로 코딩하기

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

이번에 볼 문제는 백준 2079번 문제인 팰린드롬이다.
문제는 아래 링크를 확인하자.

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

모든 팰린드롬 문자열은 그 길이가 3 이상이라면 양 끝의 두 문자를 지워도 다시 팰린드롬 문자열이 됨을 상기하자.

따라서, 가운데를 담당할 문자 하나 또는 둘을 먼저 고르고 양 옆에 문자를 하나씩 이어나가 팰린드롬 성질이 깨질 때까지 살피는 것으로 주어진 문자열에 존재하는 모든 팰린드롬 문자열에 한번씩 접근할 수 있게 된다.

dp[j]를 주어진 문자열의 [0,j] 구간에 해당하는 부분문자열에 대하여 이를 최소 개수의 팰린드롬으로 분할할 때의 개수라 하면 이는 [i,j] 구간에 해당하는 부분무자열이 팰린드롬인 모든 i에 대하여 dp[i - 1] + 1의 최솟값으로 계산할 수 있음을 관찰하자.

위의 관계를 인덱스를 노드, [i,j] 구간을 i에서 j+1로 향하는 에지로 하는 그래프로 모델링하자. 이 때 주어진 문제는 0번 인덱스에서 (문자열의 길이)번 인덱스까지 향하는 최단거리 문제로 바꾸어 생각할 수 있게 된다. BFS 등을 이용해 해당하는 최단거리를 구하고 문제를 해결하자.

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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

string s; int slen;
vector<int> G[2001];
int dist[2001];

void bfs() {
	queue<int> que;
	que.push(0);

	while (!que.empty()) {
		int cur = que.front(); que.pop();
		for (auto& nxt : G[cur]) {
			if (dist[nxt]) continue;
			dist[nxt] = dist[cur] + 1;
			que.push(nxt);
		}
	}
}

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

	cin >> s; slen = s.length();
	for (int mid = 0; mid < slen; mid++) { // 홀수길이 팰린드롬
		int L = mid, R = mid;
		while (-1 < L && R < slen && s[L] == s[R]) {
			G[L].emplace_back(R + 1);
			L--, R++;
		}
	}
	for (int midL = 0, midR = 1; midR < slen; midL++, midR++) { // 짝수길이 팰린드롬
		int L = midL, R = midR;
		while (-1 < L && R < slen && s[L] == s[R]) {
			G[L].emplace_back(R + 1);
			L--, R++;
		}
	}

	bfs();

	cout << dist[slen];
}