소프티어 - 효도 여행 (Java)

0. 개요

DFS 및 LCS 문제입니다.

이 문제는 DFS 특징을 활용한 LCS 재활용입니다.

 

1. DFS 특징을 활용한 LCS 재활용

문제의 예시 트리는 아래와 같습니다.

 

DFS를 통한 좌측 두 개의 리프 노드 탐색 순서는 아래와 같습니다.

 

7번 : 1 -> 2 -> 4 -> 7

8번 : 1 -> 2 -> 5 -> 8

 

각 경로마다 문자가 주어지니 7, 8번 리프 노드까지 도달했을 때 문자는 아래와 같습니다.

7번 : ACF

8번 : AZQ

 

감이 오시나요?

 

리프 노드까지 탐색 경로에는 중첩된 부분이 있을 수 있습니다.

또, 중첩된 경로 만큼 중복되는 문자가 있습니다.

 

7번과 8번의 노드는 2번 까지의 중첩되는 경로가 존재하고,

A 문자가 공통적으로 존재합니다.

 

그렇다면,DFS 레벨에 맞게 해당 계층의 LCS만 구하면 되지 않을까요?

LCS를 구하는 코드는 아래와 같습니다.

// 행 : level, 열 : col
boolean isMatch = (s1.charAt(depth) == s2.charAt(col)); // 문자 일치 여부 확인
int tmp = dp[depth-1][col-1] + (isMatch ? 1 : 0); // 일치하면 1 증가

dp[depth][col] = max(tmp, max(dp[depth][col-1], dp[depth-1][col])); // 갱신

 

탐색 깊이를 depth라고 했을 때,

각 depth 마다 dp의 정보를 갱신하고,

리프 노드에 도달하게 된다면 정답을 구하면됩니다.

 

주의해야할 점은,

문제 조건에 의해 루트 노드는 항상 1번입니다.

이 조건을 못봐서 계속 삽질만 했습니다....

 

[구현 코드]

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

public class Main {

    private static final int MAX = 5002;
    private static final int[][] lcs = new int[MAX][MAX];

    private static int n, m, answer;
    private static String origin;
    private static List<Point>[] graph;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stz = new StringTokenizer(br.readLine());

        n = Integer.parseInt(stz.nextToken());
        m = Integer.parseInt(stz.nextToken());
        origin = br.readLine();
        graph = new List[n];

        for(int i=0; i<n; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=0; i<n-1; i++){
            stz = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(stz.nextToken()) - 1;
            int b = Integer.parseInt(stz.nextToken()) - 1;
            char c = stz.nextToken().charAt(0);

            graph[a].add(new Point(b, c));
            graph[b].add(new Point(a, c));
        }


        boolean[] visited = new boolean[n];
        visited[0] = true;
        dfs(0, 0, visited);

        System.out.println(answer);

        br.close();
    }

    private static void dfs(int node, int depth, boolean[] visited) {
        boolean isLeaf = true;

        // 노드에 연결된 간선만큼 반복
        for(int i=0; i<graph[node].size(); i++){
            Point next = graph[node].get(i);
            char c1 = next.c;

            if(visited[next.to]) continue;
            isLeaf = false;

            // lcs
            // depth에 해당하는 dp 갱신
            for(int col=0; col<origin.length(); col++){
                char c2 = origin.charAt(col);
                lcs[depth+1][col+1] = Math.max(lcs[depth][col] + ((c1 == c2) ?  1 : 0), Math.max(lcs[depth+1][col], lcs[depth][col+1]));
            }

            visited[next.to] = true;
            dfs(next.to, depth+1, visited);
        }

        if(isLeaf){
            for(int j=0; j<origin.length(); j++){
                answer = Math.max(answer, lcs[depth][j+1]);
            }
        }
    }

    private static class Point{
        int to;
        char c;

        public Point(int to, char c) {
            this.to = to;
            this.c = c;
        }
    }
}