C++ / 백준 / 17609 / 회문

문제

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

17609번: 회문

문제풀이

왼쪽, 오른쪽, 문자를 삭제한 개수의 정보를 갖는 DFS함수를 만들어서 풀었다.

 

문자열을 입력받고 왼쪽은 0, 오른쪽은 문자열 길이-1, 삭제한 문자열 개수는 0으로 둔다.

왼쪽이 오른쪽을 넘어서면 탐색을 다 했으므로 answer값을 최솟값으로 갱신한다.

왼쪽 문자와 오른쪽 문자가 같으면 각각 한 칸씩 옮기고 DFS함수를 실행한다.

 

왼쪽문자와 오른쪽문자가 다를 경우 조건을 확인하고 만족하면 조건문을 실행한다.

왼쪽 문자를 한 칸 옮겨서 오른쪽문자와,

오른쪽 문자를 한 칸 옮겨서 왼쪽문자와 비교하는 조건문이다.

 

탐색이 끝났으면 답을 출력한다.

 

코드

#include <iostream>
#include <string>
using namespace std;
string s;
int answer;

void DFS(int left, int right, int cnt) {
	if (left >= right) {
		answer = min(answer, cnt);
		return;
	}
	else if (cnt >= 2) {
		return;
	}
	else if (s[left] != s[right]) {
		if (s[left + 1] == s[right])
			DFS(left + 1, right, cnt + 1);
		if (s[left] == s[right - 1])
			DFS(left, right - 1, cnt + 1);
	}
	else {
		DFS(left + 1, right - 1, cnt);
	}
}

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

	int T(0);
	cin >> T;
	while (T--) {
		cin >> s;
		answer = 2;
		DFS(0, s.size() - 1, 0);
		cout << answer << '\n';
	}
}