Softeer [Level 3] 효도 여행 {언어 : JavaScript} [시간초과 해결]

문제 링크

https://softeer.ai/practice/7649

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

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});
// 트리
let [n, m] = [0, 0];
let fatherString = ""; // 길이가 M인 문자열 S
const lines = [];

let idx = 0;
rl.on('line', (line) => {
    if (idx === 0) {
        [n, m] = line.split(" ").map((e) => Number(e));
    } else if (idx === 1) {
        fatherString = line;
    } else {
        lines.push(line.split(" "));
    }
    idx++;
}).on('close', () => {
    let maxHappiness = 0;
    const adjL = Array.from({length: n+1}, () => []);
    for (let i = 0; i < n-1; i++) {
        const line = lines[i];
        const [u, v] = line.slice(0, 2).map((e) => Number(e));
        const c = line[2];
        adjL[u].push([v, c]);
        adjL[v].push([u, c]);
    }
    const dfs = (depth, parent, son, visited) => {
        const result = visited[m];
        if (maxHappiness < result) {
            maxHappiness = result;
        }
        if (maxHappiness === m) {
            return;
        }
        
        for (const [grandSon, alpha] of adjL[son]) {
            if (parent === grandSon) {
                continue;
            }
            // alpha 찾기
            const stack = Array(m+1).fill(0);
            // 현재 루트가 유효할 때 : 첫 번째 시작하는 지점이 1번 정점을 지날 때
            let isValid = false;
            if (depth === 0) {
                for (let jdx = 1; jdx < m+1; jdx++) {
                    const fa = fatherString[jdx-1];
                    if (fa === alpha) {
                        isValid = true;
                        stack[jdx] = visited[jdx-1] + 1;
                    } else {
                        stack[jdx] = stack[jdx-1];
                    }
                }
            } else {
                isValid = true;
                for (let jdx = 1; jdx < m+1; jdx++) {
                    const fa = fatherString[jdx-1];
                    if (fa === alpha) {
                        stack[jdx] = visited[jdx-1] + 1;
                    } else {
                        stack[jdx] = Math.max(visited[jdx], stack[jdx-1]);
                    }
                }
            }
            if (isValid) {
                dfs(depth+1, son, grandSon, stack);
            }
        }
    }
    
    dfs(0, 0, 1, Array(m+1).fill(0));
    console.log(maxHappiness);
    process.exit(0);
});

풀이 방법

 

1. dfs 함수는 depth, parent, son, visited를 매개변수로 하여 재귀적으로 호출되며, 각 정점을 방문한다.
2. visited 배열은 fatherString과 일치하는 부분 문자열의 길이를 누적하며, stack 배열을 통해 일치 여부를 저장하고 갱신한다.
   1. 이 부분도 이전 코드에서 볼 수 있듯이 전부 저장하고 계산하는 방법도 있을 수 있지만 어차피 문자열을 더해나가는 구조로 dfs가 작동되기 때문에 바로 계산하는 것이 유리하다.
   2. 바로 계산한다는 말은 lcs를 현재 누적된 visited에 현재의 알파벳과 fatherString을 비교해서 갱신한다는 말이다.
3. 각 간선 알파벳이 fatherString의 해당 위치에 있는 문자와 일치할 경우 stack을 갱신하고, 일치하는 최대 길이를 maxHappiness에 기록한다.
4. 각 노드에서 maxHappiness가 m에 도달하면 탐색을 종료한다.
   
   1. 이 부분이 시간초과를 해결한 부분인데 애초에 maxHappiness라는게 아버지의 문자를 기반으로 산출되기 때문에 아버지의 문자길이인 m보다 길 수가 없다.
   2. 따라서 같아지면 모든 탐색을 종료한다.
5. 모든 DFS 탐색이 완료되면, maxHappiness에 저장된 최대 일치 길이를 출력한다.

 

느낀점