[BOJ 26305] AibohphobiA

문제: https://www.acmicpc.net/problem/26305

 

풀이:

길이가 $4$ 이상인 palindrome이 있으면, 앞 뒤에 두 문자를 떼어낸 문자열도 palindrome입니다. 그러므로, 우리는 길이 $2$ 혹은 $3$의 palindrome이 생기지 않도록 유지해주기만 하면 됩니다.

DP의 상태를 현재 위치 $(r, c)$와, 현재 위치에 오기 전에 방문했던 문자 $p$ 로 저장합니다. $(r, c, p) \rightarrow (nr, nc, np)$ 로의 transition은 $\lvert r-nr \rvert + \lvert c-nc \rvert = 1$ 이고, $A[r, c] = np$ 이며, $A[nr, nc]$ 가 $p$와 $A[r, c]$ 모두와 다를 때 이루어지게 됩니다. 상태의 개수는 $4NM$을 넘지 않습니다. ($p$는 $(r, c)$와 인접한 칸 중 한 문자입니다)

 

이제 상태로 만들어진 Directed graph가 주어졌을 때, $(0, 0, NULL)$ 에서 $(N-1, M-1, *)$ 로 도달하면서 중간에 $(r_i, c_i, *)$을 방문하는 가장 긴 경로를 찾으면 됩니다. 경로가 무한할 수 있고 이는 사이클을 계속 도는 것이므로 SCC를 묶어서 생각해줍시다. 이 이후에 도착점부터 시작하면서 역순으로 DP를 돌리면서 "현재 상태에서 $(N-1, M-1, *)$ 에 도달하는 최장 경로", "현재 상태에서 $(r_i, c_i, *)$을 방문하면서 $(N-1, M-1, *)$에 방문하는 최장 경로" 두 개의 상태를 저장해주면 됩니다.

 

코드: https://www.acmicpc.net/source/share/855d59872418417c881f35054572ec86