[softeer] 효도 여행

02 May 2023 in Algorithm on Algorithm

https://softeer.ai/app/assessment/index.html?xid=462882&xsrfToken=t8oWJ2GADMdAkuWjCcNeZ0fkAbhAxcxT&testType=practice

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

public class Main {

    static final int MAX = 5002;
    static Map<Integer,Map<Integer,String>> m = new HashMap<>();
    static boolean[] visited;
    static int result;
    static String S;
    static int[][] lcs = new int[MAX][MAX];

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        S = sc.next();
        visited = new boolean[N + 1];

        for (int i = 0; i < N - 1; i++) {
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();
            String text = sc.next();

            m.computeIfAbsent(n1, k -> new HashMap<>()).put(n2, text);
            m.computeIfAbsent(n2, k -> new HashMap<>()).put(n1, text);
        }

        visited[1] = true;
        dfs(1, 0);

        System.out.println(result);
    }

    static void dfs(int idx, int depth) {
        boolean isNext = false;
        Map<Integer, String> innerMap = m.get(idx);
        for (Integer k : innerMap.keySet()) {
            if (!visited[k]) {
                isNext = true;
                visited[k] = true;

                // 문자 하나만 있기 때문에 char 뽑기
                char c = innerMap.get(k).charAt(0);

                // LCS 누적 계산
                for (int j = 0; j < S.length(); j++) {
                    char sj = S.charAt(j);
                    lcs[depth + 1][j + 1] = Math.max(
                            lcs[depth][j] + ((c == sj) ? 1 : 0),
                            Math.max(lcs[depth + 1][j], lcs[depth][j + 1])
                    );
                }

                dfs(k, depth + 1);
            }
        }

        if (!isNext) {
            for (int j = 0; j <= S.length(); j++) {
                result = Math.max(result, lcs[depth][j]);
            }
        }
    }
}