[백준 BOJ 17218 glod5 - 비밀번호 만들기] Longest Common String (LCS) C++

백준 17218 https://www.acmicpc.net/problem/17218

17218번: 비밀번호 만들기

이렇게 두개의 문자열에서 가장 긴 공통 수열을 찾고, 그 수열을 출력해야 하는 문제이다.

 

2차원 배열을 이용한 dp로 해결할 수 있다. 

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>
#include <string>
#include <string.h>
#include <iostream>

using namespace std;

int alpha[41][41];
char str1[41];
char str2[41];
int back[41][41];
vector <char> LCS;

void backtracking(int x, int y) { //백트래킹

	if (x <= 0 || y <= 0) return;

	if (back[x][y] == 1) backtracking(x, y - 1);
	else if (back[x][y] == 2) backtracking(x - 1, y);
	else if (back[x][y] == 3) {
		LCS.push_back(str2[x]);
		backtracking(x - 1, y - 1);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	string s1;
	string s2;
	cin >> s1 >> s2;

	int M = s1.length();
	int N = s2.length();

	for (int i = 0; i < s1.length(); i++) {
		str1[i+1] = s1[i];
	}
	for (int i = 0; i < s2.length(); i++) {
		str2[i + 1] = s2[i];
	}
	
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= M; j++) {
			if (str1[j] == str2[i]) {
				alpha[i][j] = alpha[i-1][j-1]+ 1;
				back[i][j] = 3; //왼쪽위에
			}
			else {
				alpha[i][j] = max(alpha[i - 1][j], alpha[i][j - 1]);
				int up = alpha[i - 1][j];
				int left = alpha[i][j - 1];
				
				if (up == left || left > up) back[i][j] = 1; //왼쪽
				else if (up > left) back[i][j] = 2; //위쪽
				
			}
		}
	}
	backtracking(N, M);

	for (int i = LCS.size() - 1; i >= 0; i--) {
		cout << LCS[i];
	}
}

 

	S	E	T	A	P	P	L	E
E	0	1	1 (k)	1	1	1	1	1
A	0	1	1 (a)	2 (b)
T
M
A
N
Y								3

(a) : T와 A는 다르므로, dp[i-1][j]와 dp[i][j-1] 중에서 더 큰 값을 가져온다. 즉, 현재 위치에서 위쪽, 왼쪽 값을 비교해서 더 큰 값을 가져온다. 같을 경우에는 왼쪽에서 가져오게 했다. (이때 값을 가져오는 방향을 또 다른 하나의 배열에 저장한다. 공통 수열을 출력하기 위해 후에 백트래킹에 필요하다. 이 코드의 경우 back 배열이다)

(b) : A == A , 같은 알파벳일때는 dp[i-1][j-1] + 1 을 넣어준다. 즉 이 표에서는 (k) 값 +1 을 (b)에 넣어준다. 

 

dp[N][M] 에 있는 수가 두 수열의 가장 긴 공통 수열의 길이가 된다.

 

이 문제에서는 길이가 아니라 공통 수열을 출력해야 하므로 표를 채우면서 저장했던 값 가져오는 방향을 이용한다. dp[N][M] 에서부터 방향대로 백트래킹을 하면서, (b)처럼 값을 갱신한 경우의 알파벳을 저장하면 LCS가 된다.