[Python] 백준 1053 팰린드롬 공장

문제 링크 : https://www.acmicpc.net/problem/1053

1053번: 팰린드롬 공장

1. 접근 방법

어떤 문자열을 팰린드롬으로 만드는데, 사용할 수 있는 연산이 총 4가지가 있어 처음에는 일반적인 백트래킹으로 접근했다. 하지만 과정마다 팰린드롬임을 확인하는 것이 많은 시간이 필요하고, 각 연산을 문자열의 몇 번째 위치에서 적용할지도 고민해야 할 문제였다. 그래서 백트래킹이 아닌 재귀를 활용한 DP로 접근해 보았다.

---

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/1000/1000/1053.py

📕코드 해설
주어진 문자열로부터 새로운 문자열을 만드는 과정대신에 한 문자열의 가장 왼쪽, 오른쪽에서 부터 팰린드롬인지 확인하고 변경할 수 있다. 이는 주어진 연산이 각 위치에서 문자를 삽입, 삭제, 교환 및 서로 다른 두 문자를 교환하는 게 모두 가능하기 때문이다.

예를 들어 abbb와 같은 문자열이 주어졌다면 모든 연산을 각 문자 위치마다 적용하며 진행할 수도 있지만, 가장 왼쪽, 오른쪽의 쌍을 확인하는 방식으로 해결할 수 있다. 처음으로 (a, b) 쌍을 만나는데, 만약 이 쌍이 다르다면 하나의 문자를 삭제하거나(abbb → abb 또는 bbb 형태로 변경), 왼쪽 문자를 오른쪽에 또는 오른쪽 문자를 왼쪽게 추가하는 방법(abbb → babbb 또는 abbba 형태로 변경), 두 문자 중 하나를 다른 문자로 변경하는 방법(abbb → bbbb 또는 abba 형태로 변경)이 가능하다.

 

만약 문자를 삽입하는 경우, 삽입된 문자를 쌍으로 팰린드롬이 가능하므로 다음 단계로 나아간다. 예를 들어 abbb → abbba로 변경한 경우, 좌우의 끝은 팰린드롬 쌍이 되므로 bbb만 확인하면 된다. abbb → babbb로 변경한 경우, 역시 좌우의 끝이 팰린드롬 쌍으로 되므로 abb를 확인하면 된다.
문자를 삭제하는 경우는, 삭제한 쪽에서 중간으로 하나 더 들어가서 확인한다. 예를 들어 abbb → abb로 변경한 경우 왼쪽, 오른쪽 쌍이 (a, b)가 되어 다시 확인한다. abbb → bbb로 변경한 경우 왼쪽, 오른쪽 쌍이 (b, b)가 된다.
문자열 교환은 어떤 문자에 적용하던지 팰린드롬 쌍으로 만들 수 있다. 즉 abbb → abba로 바꾸는 경우와 abbb → bbbb로 바꾸는 경우 모두 왼쪽, 오른쪽 끝은 같은 문자의 쌍이 되므로 이를 제거한 bb만 확인하면 된다.
두 문자를 교환하는 경우는 abbb → bbba로 바뀌어지게 되고, 위의 연산으로 다시 진행하면 된다. 다만, 교환하는 연산을 한 번만 적용할 수 있으므로 연산을 사용했다는 것을 기록해야 한다. 이를 각 단계마다 확인하는 대신, 가장 먼저 적용한 후, 3가지 연산만 적용하는 방식으로 진행했다.

def palindrome_factory(left: int, right: int) -> int:
    global s, dp
    if dp[left][right] != -1:
        return dp[left][right]
    if left >= right:
        return 0
    dp[left][right] = min(
        palindrome_factory(left + 1, right) + 1,
        palindrome_factory(left, right - 1) + 1,
        palindrome_factory(left + 1, right - 1) + (s[left] != s[right]),
    )
    return dp[left][right]


if __name__ == "__main__":
    s = list(input().strip())
    l = len(s)
    dp = [[-1] * l for _ in range(l)]
    ans = palindrome_factory(0, l - 1)
    for i in range(l - 1):
        for j in range(i + 1, l):
            s[i], s[j] = s[j], s[i]
            dp = [[-1] * l for _ in range(l)]
            ans = min(ans, palindrome_factory(0, l - 1) + 1)
            s[i], s[j] = s[j], s[i]
    print(ans)

코드와 함께 다시 설명하면 다음과 같다.
DP는 dp[left][right]로 접근하게 되고, 이는 left 인덱스와, right 인덱스에 대하여 몇 번의 연산으로 완성할 수 있는지 저장한다.
우선 문자열의 왼쪽, 오른쪽의 인덱스를 두고, 탐색한다. 만약 그 경우의 수를 탐색했다면, 경우의 수를 반환한다. left와 right가 같거나, left가 더 크다면 이미 팰린드롬을 만들었기 때문에 0을 반환한다.
아니라면 탐색을 하는데, 문자열을 삽입, 삭제하는 것은 같은 연산으로 적용할 수 있다. 예를 들어 abbb가 입력되었고, 인덱스를 왼쪽부터 0이라고 하자. 그러면 처음에는 left=0, right=3으로 시작하는데, 왼쪽을 삭제하는 연산을 하면 실제로 제거하는 대신 left=1로 바꾸어 다음 연산을 이어가면 된다. 한편 오른쪽에 a를 추가하는 경우에도 실제로 추가하는 대신, 새로 추가한 a와 왼쪽의 a가 팰린드롬 한 쌍이 되므로 left=1로 바꾸면 된다. 즉 삽입과 삭제는 같은 방식으로 처리할 수 있고, 왼쪽과 오른쪽 끝에서 완성된 문자열들만 만들어가면 된다. 다른 문자로 교환하는 경우, left, right의 인덱스가 다른 경우에만 경우의 수에서 1 더하여 더 안쪽의 문자열만 확인하면 된다.
마지막 4번 연산은 재귀 함수에서 적용하는 대신, 원래 문자열에서 모든 2개 쌍에 적용한 후 나머지 1, 2, 3번 연산만 사용하여 답을 구한다.

---

3. 생각 정리

많이 사용되지는 않지만, 종종 사용되는 재귀함수를 활용한 DP구성은 조금 더 연습과 고민이 필요할 것 같다. 그 과정을 풀어가는 것은 비교적 쉽게 접근했지만, DP구성은 고민을 했다.