프로그래머스 [Lv. 2] 도넛과 막대 그래프 {언어 : JavaScript} [반례 포함]

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/258711?language=javascript

프로그래머스

정답 코드

function solution(edges) {
    const n = 1000001;
    const answer = [0, 0, 0, 0]; // 정점, 도넛, 막대, 8자
    const adjL = Array.from({length: n+1}, () => []);
    const visited = Array.from({length: n+1}, () => false);
    const inAndOut = Array.from({length: n+1}, () => [0, 0]); // [나감, 들어옴]
    edges.forEach(([start, to]) => {
        adjL[start].push(to);
        inAndOut[start][0] += 1;
        inAndOut[to][1] += 1;
    });
    // 나간게 가장 많고 들어온 것은 없는 정점이 생성한 정점
    let [createdNode, nodeCnt] = [0, 0];
    inAndOut.forEach(([cntOut, cntIn], idx) => {
        if (nodeCnt < cntOut && cntIn === 0) {
            createdNode = idx;
            nodeCnt = cntOut;
        }
    })
    // 정점 저장
    answer[0] = createdNode;

    // 탐색
    adjL[createdNode].forEach((outNode) => {
        // 현재의 돈넛 모양은 무엇인가
        let shape = 0;
        // 현재 지점이 두 갈래 길로 되어있다면 볼것도 없이 8자 모양
        if (adjL[outNode].length === 2) {
            shape = 3;
        } else {
            const stack = [outNode];
            visited[outNode] = true;

            // 출발 지점으로 돌아왔는가?
            let canReturn = false;
            // 두 갈래 길로 되어있는가?
            let hasTwoWays = false;
            
            while (stack.length) {
                const currentNode = stack.pop();
                for (const nextNode of adjL[currentNode]) {
                    if (visited[nextNode]) {
                        // 일단 막대는 아님
                        canReturn = true;
                        continue;
                    }
                    // 가는 길이 2개 인가
                    if (adjL[nextNode].length === 2) {
                        hasTwoWays = true;
                    }
                    visited[nextNode] = true;
                    stack.push(nextNode);
                }
            }
            if (canReturn) {
                if (hasTwoWays) {
                    // 8자 모양
                    shape = 3;
                } else {
                    // 도넛 모양
                    shape = 1;
                }
            } else {
                shape = 2;
            }
        }
        
        answer[shape] += 1;
    })
    
    return answer;
}

풀이 방법

1. 반복을 통해서 생성한 정점을 찾는다.
   • 정점은 In은 없고 Out만 있으며 최소 2개 이상이기 때문에 Out이 없는 In이 가장 많은 것이 생성한 정점이 된다.
2. 생성한 정점과 연결된 정점에서 그래프의 모양을 조사한다.
   • 현재의 위치에서 이미 두 갈래 길로 나눠진다면 8자 모양밖에 없다.
   • 그래프를 탐색하는데 이미 방문한 곳을 다시 방문한다면 8자 모양과 도넛 모양 중에서 고를 수 있게 canReturn을 true로 바꾼다.
   • 탐색 중에 또 두 갈래 길이 생기면 탐색을 종료하고 hasTwoWays를 true로 바꾼다.
   • 조사가 끝나면
     1. canReturn이 false이면 되돌아 오지 않는 그래프 = 막대
     2. canReturn이 true이면 8자 모양 또는 도넛
        1. hasTwoWays가 true면 두 갈래 길이 있다 = 8자
        2. 아니면 = 도넛
   • shape에 따라서 개수를 더해주면 끝!

느낀점

• 전에 풀었을 때는 감도 안잡혔는데 이제는 쉽게 느껴진다.
• 다시 풀어보면 좋겠다고 생각한 이유는 리팩토링이 필요해서이다.
  • 8자 모양인 것을 알면 굳이 탐색을 이어갈 필요가 없다. => 중간에서 멈추게 하면 좋을듯
• 중간에 n을 edges.length로 했는데 정점은 1부터 100만 까지이며 n이 4라고 해도 정점이 10만, 99만 이렇게 나올 수 있다.
  • 만약 런타임 에러가 나온다면 대부분 인덱스 에러이며 다음과 같은 반례를 유추할 수 있다.
  • edges = [[1000, 20], [5555, 20], [9876, 9876], [1000, 9876]]
  • result = [1000, 1, 1, 0]