[C/C++] 백준 9252: LCS 2 (Backtrace)

9252: Backtrace

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

9252번: LCS 2

 

풀이?

 문제에서도 친절히 적혀있다싶이 LCS(Longest Common Subseuqence)를 구하면 되는데 이는 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

 

LCS 길이 알고리즘

 무식하게 모든 경우의 수를 따지면서 풀 경우 문자열의 길이가 n,m(n<m)인 문자열이 있을 때 모든 n의 부분 수열에 대해서 m인 문자열과의 공통 부분 수열을 구해야하므로 최소  O(2^n)의 시간복잡도를 가지기 떄문에 사실상 문제를 해결할 수 없다.

 이 문제를 푸는 방법은 Dynamic Programming을 이용하여 두 문자열의 부분 수열이 되는 수열 중 긴 것을 각 지점마다 저장하는 것이다. 이때 각 지점마다 가장 긴 것 수열의 길이를 구하는 것은 3개의 값을 비교하여 가장 큰 값을 저장하면 된다. 이는 아래 코드와 같이  구현이 된다.

graph[j][i]=max(max(graph[j][i-1],graph[j-1][i]),graph[j-1][i-1]+(arr1[j-1]==arr2[i-1]));

 알고리즘 동작 방식을 간단하게 설명하면 A문자열에 i번째, B문자열에 j번째일 때 까지의 최대 길이를 구할 때 (1.)A문자열에 i-1번째와 B문자열에 j번째까지의 최대길이, (2) A문자열의 i번째와 B문자열의 j-1번째까지의 최대길이, (3) A문자열의 i-1번째와 B문자열의 j-1번째까지의 최대길이에 A문자열의 i번째와 B문자열의 j번째 문자가 같다면 +1을 해준 값 중에 최대값을 고르면 된다.

 1)과 2)는 A문자열에 i번째와 B문자열의 j번째가 어떤건지와 상관없이 후보가 된다. 다만 3) 같은 경우에는 두 문자가 같다면 부분 수열이 되는 길이가 하나 추가된 것이기 때문에 +1을 해주면 된다. 이 3가지 후보 중에 가장 긴 경우가 답이 된다.

 쉽게 정리하자면 기준 값에서 max(위의 값,왼쪽 값,왼쪽 위 대각선 값+(1 ||0))이 된다.

 

이와 같이 식이 나타내지는 이유는 아래의 표를 보면서 이해하면 된다. 문제에 예제 입력 1을 예로 들겠다. 

		C	A	P	C	A	K
	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0
A	0
Y	0
K	0
P	0

 위와 같은 경우에 빨간색으로 칠해진 부분을 보면 C가 서로 같기 때문에 파란색 부분에서 +1을 한 값이 3가지 경우 중에서 가장 큰 값이 된다. 이 1을 경계로 오른쪽에 있는 수들은 모두 왼쪽 값이 가장 큰 값이므로 1이 된다

 

 

		C	A	P	C	A	K
	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0
Y	0
K	0
P	0

  위 표에서 빨간색으로 칠해진 부분이 문자가 서로 같아 파란색으로 칠해진 부분에서 +1을 한 부분이 된다.

		C	A	P	C	A	K
	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0
P	0

이 표도 마찬가지로 Y까지 비교해보았을 때 위,왼쪽,왼쪽 위 대각선에서 오는 값을 비교해서 표를 채우면 된다.

		C	A	P	C	A	K
	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

결국 완성한 표는 다음과 같아진다. 이렇게 표를 만들어 놓게 되면 시간이 O(N*M)이 되므로 제한된 시간내에 풀 수 있으며 모두의 부분 수열이 되는 수열 중 가장 긴 길이가 graph[n][m]이 된다.

 

 

Backtrace 구현!

 Backtrace 구현은 기존 값이 어디서 왔는지 back[][]배열에 저장하여 나타내는데 1이라면 왼쪽에서, 2라면 위쪽에서, 3이라면 대각선에서 온 것을 의미한다. 저장한 후에 가장 오른쪽 아래 값, 즉 graph[n][m]에서부터 backtrace를 시작한다. 이때 backtrace[] 배열에는 back[][] 베열에 3이 저장되어 있을 때 값을 저장하면 된다. 그 이유는 대각선에서 온다는 뜻은 두 문자열에 같은 문자끼리 맞아 부분 수열의 길이가 +1 되기 때문에 이 +1이 되는 순간이 곧 LCS의 원소가 되는 것이다. 

 표에서 나타내면 다음과 같다.

 

		C	A	P	C	A	K
	0	0	0	0	0	0	0
A	0	0	1	1	1	1	1
C	0	1	1	1	2	2	2
A	0	1	2	2	2	3	3
Y	0	1	2	2	2	3	3
K	0	1	2	2	2	3	4
P	0	1	2	3	3	3	4

 따라서 이 경우에 LCS는 ACAK가 된다. 

 

 

 

소스코드!

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

int graph[1001][1001];
char backtrace[1002];
int back[1001][1001];


int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  string arr1,arr2;
  cin>>arr1>>arr2;
  int n=arr1.length(),m=arr2.length();
  for(int j=1;j<=n;j++){
    for(int i=1;i<=m;i++){
      graph[j][i]=max(max(graph[j][i-1],graph[j-1][i]),graph[j-1][i-1]+(arr1[j-1]==arr2[i-1]));
      if(graph[j][i-1]==graph[j][i]) //왼쪽으로
        back[j][i]=1;
      else if(graph[j-1][i]==graph[j][i])
        back[j][i]=2;
      else
        back[j][i]=3; //대각선
    }
  }
  
  int result=graph[n][m];
  cout<<result<<"\n";  
  if(result==0)
    return 0;
  
  int tmp=result,y=n,x=m,next=back[y][x];
  while(result!=0){
      if(next==1)
        next=back[y][--x];
      else if(next==2)
        next=back[--y][x];
      else{
        backtrace[result--]=arr2[x-1];
        next=back[--y][--x];
      }
    }
  
  for(int i=1;i<=tmp;i++)
    cout<<backtrace[i];  
}