Softeer [Level 3] [HSAT 6회 정기 코딩 인증평가 기출] 출퇴근길 {언어 : JavaScript} [다시 풀어 볼것, 런타임에러 해결]

알고리즘/다시 풀어 보기

Softeer [Level 3] [HSAT 6회 정기 코딩 인증평가 기출] 출퇴근길 {언어 : JavaScript} [다시 풀어 볼것, 런타임에러 해결]

스위태니 2024. 10. 31. 21:17

문제 링크

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

softeer.ai

정답 코드

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

const inputData = [];

rl.on('line', (line) => {
    inputData.push(line.split(" ").map((e) => Number(e)));
}).on('close', () => {
    const [n, m] = inputData[0];
    const nAdjL = Array.from({length: n+1}, () => []);
    const rAdjL = Array.from({length: n+1}, () => []);
    for (let i = 1; i <= m; i++) {
        const [st, to] = inputData[i];
        nAdjL[st].push(to);
        rAdjL[to].push(st);
    }
    const [s, t] = inputData[m+1];
    const dfs = (start, visited, adjL) => {
        const stack = [start];
        visited[start] = 1;  // 시작 노드 방문 표시
        while (stack.length > 0) {
            const node = stack.pop();
            for (const nextNode of adjL[node]) {
                if (!visited[nextNode]) {
                    visited[nextNode] = 1; // 방문 표시
                    stack.push(nextNode);
                }
            }
        }
    }

    const fromS = Array(n+1).fill(0);
    const fromT = Array(n+1).fill(0);
    const toS = Array(n+1).fill(0);
    const toT = Array(n+1).fill(0);

    fromS[t] = 1;
    dfs(s, fromS, nAdjL);
    fromT[s] = 1;
    dfs(t, fromT, nAdjL);
    dfs(s, toS, rAdjL);
    dfs(t, toT, rAdjL);

    let cnt = 0;
    for (let i = 1; i <= n; i++) {
        if (fromS[i] && fromT[i] && toS[i] && toT[i]) {
            cnt += 1;
        }
    }
    console.log(cnt-2);
    process.exit(0);
});

풀이 방법

인접 리스트 생성
- nAdjL: 각 노드에 연결된 노드를 저장하는 정방향 인접 리스트
- rAdjL: 각 노드에 역방향으로 연결된 노드를 저장하는 역방향 인접 리스트
  - 문제는 s에서 출발해서 t까지 도달하고, t에서 다시 s로 돌아오는 양방향 경로가 있는 노드를 찾는 것.
  - nAdjL로 s에서 t까지 도달 여부를 확인하고, rAdjL로 역방향 탐색을 통해 다시 돌아오는 경로를 탐색가능.
DFS 탐색 함수 정의 (반복형)
- dfs: 반복형 DFS 함수로, 주어진 start 노드에서 출발해 연결된 모든 노드를 탐색한다.
- visited: 방문 여부를 저장하는 배열이다. 이미 방문한 노드는 다시 방문하지 않는다.
- adjL: 탐색에 사용할 인접 리스트 (정방향 또는 역방향)를 매개변수로 받아 동적으로 지정할 수 있게 했다.
각 방향별 방문 여부를 저장하는 배열 설정
- fromS: s에서 출발하여 도달 가능한 노드를 기록 (nAdjL을 사용).
- fromT: t에서 출발하여 도달 가능한 노드를 기록 (nAdjL을 사용).
- toS: s로 돌아올 수 있는 노드를 기록 (rAdjL을 사용).
- toT: t로 돌아올 수 있는 노드를 기록 (rAdjL을 사용).
- fromS[t] = 1와 fromT[s] = 1은 출발점 s에서 t로 가는 경로와 도착점 t에서 s로 돌아오는 경로가 각각 유효한지 확인하기 위해, t와 s를 미리 방문한 노드로 설정하는 것
각 경로의 도달 여부 탐색
- dfs(s, fromS, nAdjL): s에서 출발하여 정방향 탐색을 통해 t까지 도달할 수 있는 노드를 fromS에 기록.
- dfs(t, fromT, nAdjL): t에서 출발하여 정방향 탐색을 통해 e까지 도달할 수 있는 노드를 fromT에 기록.
- dfs(s, toS, rAdjL): s에서 출발하여 s로 돌아올 수 있는 노드를 역방향 탐색하여 toS에 기록.
- dfs(t, toT, rAdjL): t에서 출발하여 t로 돌아올 수 있는 노드를 역방향 탐색하여 toT에 기록.
fromS[i] && fromT[i] && toS[i] && toT[i]가 모두 1인 경우 cnt에 1을 더해주고 cnt를 출력하면 끝!
- 출발지와 도착지를 빼야 하므로 -2까지 하면 정말 끝!

JavaScript의 재귀 깊이 문제점

JavaScript의 재귀 깊이는 런타임과 엔진에 따라 다르지만, 일반적으로 Node.js에서는 약 10,000회에서 20,000회 정도로 제한된다. Chrome V8 엔진을 사용하는 경우, 이 정도 수준에서 RangeError: Maximum call stack size exceeded 오류가 발생할 수 있다. 따라서 기존의 코드에서 stack을 사용하는 while문으로 변경해서 dfs를 활용하는 것이 좋다. 아래는 런타임이 발생한 코드이다.

const dfs = (start, visited, adjL) => {
    if (visited[start]) {
        return;
    }
    visited[start] = 1;
    for (const nextN of adjL[start]) {
        dfs(nextN, visited, adjL);
    }
    return;
}

느낀점

아직 정방향 역방향에 대한 이해도가 떨어지는 것 같다.
출발지점에서 끝지점까지, 끝지점에서 출발지점까지 도달하는지 확인하고
출발지에서 출발지로 돌아오는지, 끝지점에서 끝지점으로 돌아오는지 확인하는 방식이 어려웠다.
다시 풀어보는 것이 좋을 것 같은 문제이다.

저작자표시