[Softeer/DP, DFS] 효도 여행

문제

https://softeer.ai/practice/7649

Softeer - 현대자동차그룹 SW인재확보플랫폼

 

해결방법

해당 문제는 DFS로 그래프 순환 및 LCS구현을 통해 해결할 수 있는 문제이다. DFS는 인접리스트를 순회하는 방법으로 쉽게 구현 가능하다. 그러나 LCS를 기본 LCS로 구현하면 O(N^3)의 시간복잡도를 가지기때문에 시간초과가 발생한다.

우선 LCS의 일반적인 코드는 아래와 같다.

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

 

위와같이 구현하게되면, 이미 구해진 LCS값을 매번 초기화하게되어 시간초과가 발생한다. 이를 해결하기위해 dp배열을 재활용하는 방식으로 LCS를 구한다. 재활용 하는 방법은 아래와 같다. 해당 방법으로 구현하면 O(N^2)로 시간초과를 해결할 수 있다.

• dp배열은 2차원으로 하며 노드의 depth와 문자열 S의 길이만큼 초기화 한다.
  • depth는 거쳐간 엣지의 길이(path) 역할
• 문자열 S를 한 자리씩 순회하여 현재 엣지의 문자와 비교한다.
• 문자가 같은 경우 좌우 대각 방향의 dp값 + 1로 값을 정의하고, 다른 경우 좌, 상의 dp값 중 큰 값으로 입력한다.

소스코드

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

public class Main {
    static class Edge{
        int v;
        char c;
        Edge(int v, char c){
            this.v = v;
            this.c = c;
        }
    }
    
    static int N, M;
    static String S;
    static List<List<Edge>> adj;
    static int[] visited;
    static int[][] dp = new int[5001][5001];
    static int answer = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] first = br.readLine().split(" ");
        N = Integer.parseInt(first[0]);
        M = Integer.parseInt(first[1]);
        S = br.readLine();        
        visited = new int[N];

        adj = new ArrayList<>();
        for(int i = 0; i < N; i++){
            adj.add(new ArrayList<>());
        }
        for(int i = 0; i < N - 1; i++){
            String[] line = br.readLine().split(" ");
            int u = Integer.parseInt(line[0]) - 1;
            int v = Integer.parseInt(line[1]) - 1;
            char c = line[2].charAt(0);

            adj.get(u).add(new Edge(v, c));
            adj.get(v).add(new Edge(u, c));
        }
        
        visited[0] = 1;
        dfs(0, 0, ' ');

        System.out.print(answer);
    }

    static void dfs(int idx, int depth, char c){
        for(int i = 0; i < S.length(); i++){
            if(S.charAt(i) == c)
                dp[depth + 1][i + 1] = dp[depth][i] + 1;
            else
                dp[depth + 1][i + 1] = Math.max(dp[depth + 1][i], dp[depth][i + 1]);
            answer = Math.max(dp[depth + 1][i + 1], answer);
        }
        
        for(int i = 0; i < adj.get(idx).size(); i++){
            Edge e = adj.get(idx).get(i);
            if(visited[e.v] == 1)
                continue;

            visited[e.v] = 1;
            dfs(e.v, depth + 1, e.c);
            visited[e.v] = 0;
        }
    }
}