BOJ G4 9252 LCS2 JAVA

9252번: LCS 2

---

문제 읽기

LCS, 즉 최장 공통 부분 수열의 길이를 찾으면서, 동시에 수열까지 구해야 하는 문제이다. 이전에 한 번 풀어봤지만 잘 기억이 나지 않아 다시 공부하면서 풀어보았다. 한 마디로 DP를 활용하면 된다.

---

문제 풀기

LCS 수열 길이 구하기

일단 점화식을 찾기 위해 그려봤다.

이런 식으로 구할 수 있다.

 

즉, 두 문자열에서 str1의 i번째 문자, str2의 j번째 문자가 같은지, 같지 않은 지에 따라서 점화식을 세워볼 수 있다.

점화식은 다음과 같다.

간단히 설명하자면, 각 문자가 같으면 왼쪽 위 대각선 값에 +1을 해주고, 각 문자가 다르면 str1의 i번째 문자만 포함했을 때의 최댓값, str2의 j번째 문자만 포함했을 때의 최댓값 중 큰 값을 넣어주면 된다.

 

또한 dp[i][0]과 dp[0][j] 인 각 첫 번째 행렬은 따로 초기화를 시켜주어야 한다.

boolean flag = false;
for (int i = 0; i < N; i++){
    if (str2[0] == str1[i]) flag = true;
    if (flag) dp[i][0] = 1;
}
flag = false;
for (int j = 0; j < M; j++){
    if (str1[0] == str2[j]) flag = true;
    if (flag) dp[0][j] = 1;
}

 

이런 식으로 DP를 조금만 활용하면 되기 때문에 LCS의 수열 길이를 찾는 것은 크게 어렵지 않다. 

 

해당 부분 코드는 다음과 같다.

for (int i = 1; i < N; i++){
    for (int j = 1; j < M; j++){
        if (str1[i] == str2[j]) dp[i][j] = dp[i-1][j-1]+1;
        else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
    }
}

 

하지만 해당 문제에서는 수열도 출력하길 요구한다.

LCS 수열 구하기

이건 계속 해봐도 잘 모르겠어서 찾아봤다! 아래 블로그에 설명이 잘 되어있었다.

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

 

위 그림의 파란색 화살표에 주목해보자.

N-1, M-1 좌표에서부터 시작해서 다음과 같은 과정을 통해 수열을 구할 수 있다.

1. 맨 오른쪽 아래인 N-1, M-1 좌표에서 시작한다.
2. 현 좌표에서 위쪽과 왼쪽 좌표를 확인한다
   1. 현 위치와 같은 값이면 이동한다.
   2. 현 위치와 다른 값이면 왼쪽 위 대각선으로 이동한다.
3. 2번을 계속 반복하면서 0을 만나면 끝낸다.

해당 부분 코드는 다음과 같다. queue를 사용하긴 했는데 굳이 안 써도 될 것 같다.

//lcs 수열 구하기
Queue<Pos> q = new ArrayDeque<>();
q.offer(new Pos(N-1, M-1));
int[] dr = {-1, 0};
int[] dc = {0, -1}; //상, 좌
while(!q.isEmpty()){
    Pos cur = q.poll();

    boolean canGo = false;
    for (int di = 0; di < 2; di++){
       int nr = cur.r + dr[di];
       int nc = cur.c + dc[di];
       if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;

       if (dp[cur.r][cur.c] == dp[nr][nc]){
		       canGo = true;
           q.offer(new Pos(nr, nc));
           break; //괜찮겠지?
       }
    }
    if (!canGo) {
        sb.append(str1[cur.r]);
        if (dp[cur.r][cur.c] == 1) break;
        q.offer(new Pos(cur.r-1, cur.c-1));
        }
    }
}

---

코드

package ps.ㄱSolving;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class BOJ_G4_9252_LCS2 {
    static class Pos{
        int r, c;
        public Pos(int r, int c){
            this.r = r;
            this.c = c;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        char[] str1 = in.readLine().toCharArray();
        char[] str2 = in.readLine().toCharArray();

        int N = str1.length;
        int M = str2.length;
        int[][] dp = new int[N][M];
        boolean flag = false;
        for (int i = 0; i < N; i++){
            if (str2[0] == str1[i]) flag = true;
            if (flag) dp[i][0] = 1;
        }
        flag = false;
        for (int j = 0; j < M; j++){
            if (str1[0] == str2[j]) flag = true;
            if (flag) dp[0][j] = 1;
        }

        for (int i = 1; i < N; i++){
            for (int j = 1; j < M; j++){
                if (str1[i] == str2[j]) dp[i][j] = dp[i-1][j-1]+1;
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
//        for (int i = 0; i < N; i++){
//            System.out.println(Arrays.toString(dp[i]));
//        }

        StringBuilder sb = new StringBuilder();
        int len = dp[N-1][M-1];
        if (len == 0){
            System.out.println(len);
            return;
        }
        //lcs 수열 구하기
        Queue<Pos> q = new ArrayDeque<>();
        q.offer(new Pos(N-1, M-1));
        int[] dr = {-1, 0};
        int[] dc = {0, -1}; //상, 좌
        while(!q.isEmpty()){
            Pos cur = q.poll();

            boolean canGo = false;
            for (int di = 0; di < 2; di++){
                int nr = cur.r + dr[di];
                int nc = cur.c + dc[di];
                if (nr < 0 || nr >= N || nc < 0 || nc >= M) continue;

                if (dp[cur.r][cur.c] == dp[nr][nc]){
                    canGo = true;
                    q.offer(new Pos(nr, nc));
                    break; //괜찮겠지?
                }
            }
            if (!canGo) {
                sb.append(str1[cur.r]);
                if (dp[cur.r][cur.c] == 1) break;
                q.offer(new Pos(cur.r-1, cur.c-1));
            }
        }

        System.out.println(len);
        System.out.println(sb.reverse());
    }
}