LCS 최장 공통 부분 수열 : 3개일 때 길이 뿐만 아니라, 부분문자열까지 찾아내기 @@황소처럼 우직하게@@

https://hjp845.tistory.com/30

백준 1958 파이썬 python : LCS 3 @@황소처럼 우직하게@@

이전 글에서 길이를 찾아내는 문제를 풀어보았다.

이번에는 부분문자열까지 찾아내는 솔루션을 제시한다.

이런 문제가 사이트에 있을진 모르겠지만, 충분히 나올 수 있는 문제다.

lst = [input() for i in range(3)]
dp = [[[0 for i in range(len(lst[0]) + 1)] for j in range(len(lst[1]) + 1)] for k in range(len(lst[2]) + 1)]

for k in range(1, len(lst[2]) + 1):
    for j in range(1, len(lst[1]) + 1):
        for i in range(1, len(lst[0]) + 1):
            if lst[0][i - 1] == lst[1][j - 1] == lst[2][k - 1]:
                dp[k][j][i] = dp[k - 1][j - 1][i - 1] + 1
            else:
                dp[k][j][i] = max(dp[k - 1][j][i], dp[k][j - 1][i], dp[k][j][i - 1], dp[k - 1][j - 1][i], dp[k][j - 1][i - 1], dp[k - 1][j][i - 1])

ans = ''
now = dp[-1][-1][-1]
k = len(dp) - 1
j = len(dp[0]) - 1
i = len(dp[0][0]) - 1
while now != 0:
    if now - 1 == dp[k - 1][j][i] == dp[k][j - 1][i] == dp[k][j][i - 1] == dp[k - 1][j - 1][i] == dp[k][j - 1][i - 1] == dp[k - 1][j][i - 1]:
        ans = lst[0][i - 1] + ans
        k -= 1
        j -= 1
        i -= 1
        now -= 1
    else:
        flag = []
        value = 0
        if dp[k - 1][j][i] > value:
            value = dp[k - 1][j][i]
            flag = [k - 1, j, i]
        if dp[k][j - 1][i] > value:
            value = dp[k][j - 1][i]
            flag = [k, j - 1, i]
        if dp[k][j][i - 1] > value:
            value = dp[k][j][i - 1]
            flag = [k, j, i - 1]
        if dp[k - 1][j - 1][i] > value:
            value = dp[k - 1][j - 1][i]
            flag = [k - 1, j - 1, i]
        if dp[k - 1][j][i - 1] > value:
            value = dp[k - 1][j][i - 1]
            flag = [k - 1, j, i - 1]
        if dp[k][j - 1][i - 1] > value:
            value = dp[k][j - 1][i - 1]
            flag = [k, j - 1, i - 1]
        k, j, i = flag

print(dp[-1][-1][-1])
print(ans)

알고리즘은 간단하다

주변 6개 칸이 현재칸 값보다 다 1씩 낮다면, 현재 문자열을 ans에 추가한다. 그리고 i - 1, j - 1, k - 1 칸으로 이동한다.

그렇지 않다면

주변 6개 칸중에서 큰 값을 찾고 그 칸으로 이동한다.

0이 되면 탐색을 종료한다.

반복문으로 깔끔하게 풀 수도 있었으나, 6개정도니 그냥 if문 6개로 풀었다.