[백준](Java) 9252 - LCS 2

문제 링크

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

문제 풀이

이전의 lcs는 최장 공통 부분 수열의 길이를 출력하는 문제였고, 이번 문제는 그 문자가 어떤 문자인지 파악하는것이었다. 해당 로직도 이전글에 링크를 걸어둔 곳에 잘 설명되어 있었다.

문자열을 구하는 과정을 bfs를 사용하여 맨 마지막에서 처음지점까지 거꾸로 가면 된다고 생각했다.
시작을 맨 마지막에서 하여 탐색은 위쪽, 왼쪽만 탐색하며 진행했다.
현재의 lcs값과 탐색한곳의 lcs 값이 같으면 그 지점의 좌표를 추가하고 더이상 탐색할일이 없으므로 바로 break로 탈출하여 다음 좌표에서 새로 탐색을 시작하며, 두 값이 다른 경우에는 현재의 값이 새로 추가된 문자열이므로 구하려고 하는 배열 lcsword에 추가해놓고 현재 좌표에서 (y,x) 에서 각각 -1을 해준곳으로 이동한다.

코드

import java.util.*;

public class Main {

    public static class Node {
        int y;
        int x;

        public Node(int y, int x) {
            this.y = y;
            this.x = x;
        }
    }

    static String[] word1;
    static String[] word2;
    static int [][] lcs;
    static String[] lcsword;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        word1 = (" " + sc.next()).split("");
        word2 = (" " + sc.next()).split("");
//        System.out.println(Arrays.toString(word1));
//        System.out.println(Arrays.toString(word2));
        lcs  = new int[word1.length][word2.length];

        for (int i = 0; i < lcs.length; i++) {
            for (int j = 0; j < lcs[0].length; j++) {
                if (i == 0 || j == 0) {
                    lcs[i][j] = 0;
                } else if (word1[i].equals(word2[j])) {
                    lcs[i][j] = lcs[i - 1][j - 1] + 1;
                } else {
                    lcs[i][j] = Math.max(lcs[i - 1][j], lcs[i][j - 1]);
                }
            }
        }

        System.out.println(lcs[lcs.length - 1][lcs[0].length - 1]);
        lcsword = new String[lcs[lcs.length - 1][lcs[0].length - 1]];

        //위, 왼쪽

        int y = lcs.length - 1;
        int x = lcs[0].length - 1;
        bfs(y, x);
        for(int i=lcsword.length-1; i>=0; i--){
            System.out.print(lcsword[i]);
        }
    }

    public static void bfs(int y, int x) {
//        System.out.println(y+" "+x);
        int[] diry = {-1, 0};
        int[] dirx = {0, -1};
        int idx = 0;
        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(y, x));
        while (!queue.isEmpty()) {
            Node now = queue.poll();
            boolean chk = true;
            for (int i = 0; i < 2; i++) {
                int now_y = now.y + diry[i];
                int now_x = now.x + dirx[i];
                if (lcs[now.y][now.x] == lcs[now_y][now_x]) {
                    queue.add(new Node(now_y, now_x));
                    chk = false;
                    break;
                }
            }

            if (chk) {
                queue.add(new Node(now.y - 1, now.x - 1));
                lcsword[idx++] = word1[now.y];
//                System.out.println(Arrays.toString(lcsword));
            }

            if (idx == lcsword.length) {
                break;
            }

        }

    }
}