[BOJ 21142] Longest Common Subsequence

문제

---

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

풀이

---

아이디어를 쥐어짜내듯 풀었다.

일반적인 2, 3개짜리 LCS는 시간 복잡도가 O(n ** 2), O(n ** 3)라 도움이 되지 않을 거라 생각했다.

일부 문자열들의 LCS 길이를 알아도 전체 LCS 길이를 구하는 데 도움이 되지 않을 것 같았다.

뭔진 모르지만 주어진 문자열들의 LCS가 있다고 쳐보자.

이 LCS는 주어진 문자열들 중 어떤 문자열을 뽑던 순방향으로 읽을 때 띄엄띄엄 등장해야 한다.

반대로 생각하면 선행 관계가 주어졌을 때 이 관계들을 만족시키는 문자열을 찾는 것이라고도 볼 수 있다.

이는 위상 정렬과 동일한 맥락이다.

하지만 위상 정렬은 DAG (Directed Acyclic Graph, 사이클 없는 방향 그래프)에서만 가능하므로 사이클을 모두 제거해 줘야 한다.

길이가 k인 n개의 문자열 각각에 대해, 총 k * (k - 1) / 2개의 (앞에 있는 문자, 뒤에 있는 문자) 쌍을 얻을 수 있다.

A부터 차례로 0, 1, …로 치환하면 k x k 인접 행렬 G를 얻을 수 있다.

이때 G[i][j] == G[j][i] == 1이면 사이클을 의미하므로 두 값 모두 0으로 바꾼다.

이후 k <= 26이므로 dfs로 탐색했다.

코드

---

import sys
sys.setrecursionlimit(10 ** 5)

n, k = map(int, sys.stdin.readline().split())
graph = [[0] * k for _ in range(k)]

for _ in range(n):
    string = list(map(lambda x: ord(x) - 65, sys.stdin.readline().strip()))
    for i in range(k - 1):
        for j in range(i + 1, k):
            graph[string[i]][string[j]] = 1

for i in range(k):
    for j in range(i + 1, k):
        if graph[i][j] == graph[j][i] == 1:
            graph[i][j] = graph[j][i] = 0


dp = [-1] * k


def f(pos):
    if dp[pos] != -1:
        return dp[pos]
    
    res = 1
    for next in range(k):
        if graph[pos][next]:
            res = max(res, 1 + f(next))
    
    dp[pos] = res
    return res


ans = 0
for start in range(k):
    ans = max(ans, f(start))
print(ans)