DP 역추적

문제

풀이

일반적으로 DP테이블을 만들어서 LCS를 찾는 것은 할 줄 알았다. 하지만 LCS의 경로를 찾는 것은 처음 접해 본 문제였다.

일단 LCS 구하는 DP 테이블이다.

DP 테이블을 갱신하면서 만약 str1[row] == str2[col]이라면 이전 dp[row - 1][col - 1]에서 개수를 가져오면 된다.
만약 str1[row] != str2[col]이라면 dp[row - 1][col], dp[row][col - 1] 중 최대값을 가져오면 된다.
이렇게 최대값을 구할 수 있다.

여기서 경로를 추적하는 방법은 이전 row, col을 저장하는 것이다.

그래서 전 경로를 추적하다가 str1[row] == str2[col]이 같으면 stack에 쌓아준다.
stack에 쌓아주는 이유는 문자열을 reverse해야하기 때문이다.
이렇게 하여 row가 범위에 벗어날 경우 종료하면 된다.

import java.io.*;
import java.util.*;

public class Solution {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("./input.txt"));
		//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
//		StringTokenizer st = new StringTokenizer(br.readLine());
		
		String str1 = br.readLine();
		String str2 = br.readLine();
		
		int N1 = str1.length();
		int N2 = str2.length();
		int[][] dp = new int[N1 + 1][N2 + 1];
		Pos[][] track = new Pos[N1 + 1][N2 + 1];
		
		for (int row = 1; row <= N1; row++) {
			for (int col = 1; col <= N2; col++) {
				if (str1.charAt(row - 1) == str2.charAt(col - 1)) {
					dp[row][col] = dp[row - 1][col - 1] + 1;
					track[row][col] = new Pos(row - 1, col - 1);
					continue;
				}
				
				if (dp[row][col - 1] > dp[row - 1][col]) {
					dp[row][col] = dp[row][col - 1];
					track[row][col] = new Pos(row, col - 1);
				} else {
					dp[row][col] = dp[row - 1][col];
					track[row][col] = new Pos(row - 1, col);
				}
			}
		}
		
		System.out.println(dp[N1][N2]);
		
		Stack<Character> stack = new Stack<>();
		
		int cur_row = N1;
		int cur_col = N2;
		
		while (cur_row > 0 && cur_col > 0) {
			if (str1.charAt(cur_row - 1) == str2.charAt(cur_col - 1)) {
				stack.push(str1.charAt(cur_row - 1));
			}
			int new_row = track[cur_row][cur_col].row;
			int new_col = track[cur_row][cur_col].col;
			cur_row = new_row;
			cur_col = new_col;
			
		}
		StringBuilder sb = new StringBuilder();
		
		while (!stack.isEmpty()) {
			sb.append(stack.pop());
		}

		System.out.println(sb.toString());
	}
	
	static class Pos {
		int row, col;
		
		Pos(int row, int col) {
			this.row = row;
			this.col = col;
		}
	}
}