[BOJ/9252/Golang] 백준 9252 - LCS 2

접근 방식

이 문제는 직전 문제인 LCS (9251) 문제와 동일합니다. 다만 한 가지 더 출력해야 하는데요. 바로 찾은 LCS의 길이 뿐만 아니라, LCS 부분 수열 자체도 출력해야 합니다.

이 문제를 보고 처음 든 생각은, 아 뭔가 부모를 찾고 찾아서 거꾸로 이동하면서 출력하면 되겠구나.. 였습니다. 하지만 부모를 찾아갈 때 어떤 조건을 기준으로 이동할 것인지 생각하는 부분이 어려웠습니다.

중요한 점은 이전에 LCS의 길이가 증가할 때를 살펴보면, [i] == B[j]인 경우였습니다. 이 경우에 D[i][j] = D[i-1][j-1] + 1을 이용할 수 있었죠.

부분 수열 자체를 찾기 위한 꼬리에 꼬리를 무는 이동 조건도 이와 유사합니다. 이 전에 D[i-1][j] 또는 D[i][j-1]은 일치하지 않는 경우에 갖게 되는 값이었습니다. 즉, D[i][j]의 값이 D[i-1][j] 또는 D[i][j-1]과 동일하다면, 이는 부분 수열에 해당하지 않는 원소일 겁니다. 그럴 땐 그냥 둘 중 아무 값으로나 이동합니다.

만약 D[i][j]와 일치하는 값이 둘 중에 없다면, 그 값이야말로 우리가 찾던 부분 수열에 해당하는 원소입니다. 따라서 이를 부분 수열 배열에 넣어줍시다. 그리고 다음으로는 D[i-1][j-1]로 이동합니다. LCS의 길이를 찾을 때도 LCS에 해당하는 D[i][j]는 D[i-1][j-1]에서 찾아왔다는 걸 생각해보면 그 역순으로 이동하고 있다는 것을 알 수 있습니다.

이렇게 쭉 이동하다가 i==j==0 이 되면, 이동을 멈추고 그 동안 모아왔던 부분 수열 배열을 역순으로 출력하면, 우리가 찾던 LCS가 출력 되는 것을 확인할 수 있습니다.

저는 부분 수열 출력을 위한 배열을 만드는 건, 위에서부터 아래로(Top→Down)으로 이동하기 때문에 재귀가 접근하기 쉬울 것으로 판단하고 아래와 같이 코드를 작성했습니다. solve() 메서드를 참고해주세요 🙂

solve() 메서드

func solve(i, j int) {
    if D[i][j] == 0 {
        return
    }
    if D[i][j] == D[i-1][j] {
        solve(i-1, j)
    } else if D[i][j] == D[i][j-1] {
        solve(i, j-1)
    } else {
        result = append(result, string(A[i]))
        solve(i-1, j-1)
    }
}

코드

package main

import (
    "bufio"
    "fmt"
    "os"
)

var (
    w  = bufio.NewWriter(os.Stdout)
    sc = bufio.NewScanner(os.Stdin)
)

var (
    A, B   string
    D      [][]int
    result []string
)

func main() {
    defer w.Flush()
    A, B = " "+scan(), " "+scan()
    n, m := len(A)-1, len(B)-1
    D = make([][]int, n+1)
    result = make([]string, 0)
    for i := range D {
        D[i] = make([]int, m+1)
    }
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if A[i] == B[j] {
                D[i][j] = D[i-1][j-1] + 1
            } else {
                D[i][j] = max(D[i-1][j], D[i][j-1])
            }
        }
    }
    fmt.Fprintln(w, D[n][m])
    solve(n, m)
    for i := len(result) - 1; i >= 0; i-- {
        fmt.Fprintf(w, "%s", result[i])
    }
    fmt.Fprintln(w)
}

func solve(i, j int) {
    if D[i][j] == 0 {
        return
    }
    if D[i][j] == D[i-1][j] {
        solve(i-1, j)
    } else if D[i][j] == D[i][j-1] {
        solve(i, j-1)
    } else {
        result = append(result, string(A[i]))
        solve(i-1, j-1)
    }
}

func scan() string {
    sc.Scan()
    return sc.Text()
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

마무리

여기까지 따라오시느라 고생 많으셨습니다. 만약 이 글이 도움이 되셨다면 글 좌측 하단의 하트❤를 눌러주시면 감사하겠습니다.

혹시라도 글에 이상이 있거나, 이해가 가지 않으시는 부분, 또는 추가적으로 궁금하신 내용이 있다면 주저 마시고 댓글💬을 남겨주세요! 빠른 시간 안에 답변을 드리겠습니다 😊