[JS] 도넛과 막대 그래프

그래프를 활용한 구현문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/258711

프로그래머스

 

 

사실 처음에 문제에 대한 접근 자체가 힘들었었다. 선형, 도넛형 , 8자형 구분을 하란건 알겠는데 중심 노드가 주어지지 않았기 때문이다. 따라서 문제를 푸는 방식을 아래와 같이 단순화 해보았다.

 

1. 중심노드 찾기 (뻗어가는 노드 찾기)

2. 중심노드에서 뻗어나간 그래프들의 종류를 찾기

 

 

1. 중심노드 찾기

중심노드를 어떻게 찾을 수 있을까 고민했는데 중심노드는 자신에게 들어오는 노드가 없으면서 본인이 2개 이상의 노드로 접근한다면 이를 중심노드로 볼 수 있지 않을까란 고민을 하고 그렇게 구현했다.

( 근데 아래와 같은 경우는 사실 잡지못하는데 테스트는 우선 통과되긴 했다.. 이건 나중에 생각해 봐야할 듯 하다.)

 

1 -> 2 <- 3   [ 1,3번 둘다 중심노드가 될 수 있음 ]

 

2. 그래프 종류 찾기

이건 그래프들의 특성을 이용하면 해결할 수 있다.

 

막대 그래프 -> 순회를 계속했을때 더이상 뻗어나갈 노드가 없는 경우

도넛 그래프 -> 순회를 계속했을때 자기자신으로 돌아온 경우

8자 그래프 -> 순회를 계속 했을때 뻗어나가는 노드가 2개짜리가 발견된 경우

 

 

visited 배열..

어차피 각 노드는 한번이상 방문할 필요가 없어서 굳이 복사해가면서 사용하지 않고 최초에 10000001 짜리 크기의 배열 하나를 만들어서 사용했다.

outGraph , inGraph는 효율적인 그래프 탐색을 위해 map자료형을 사용했다.

 

 

 

 

function solution(edges) {
    //노드에서 나가는 정보 , 들어오는 정보 저장
    const outGraph = new Map()
    const inGraph = new Map()
    const visited = new Array(10000001).fill(false)
    
    for (const [s,e] of edges){
        if(!outGraph.has(s)) outGraph.set(s,[e])
        else outGraph.get(s).push(e)
        
        if(!inGraph.has(e)) inGraph.set(e,[s])
        else inGraph.get(e).push(s)
    }
    
    const checkGraphType = (node,graph,visited) => {
        while(1){
            const nxNodes = graph.get(node)
            if (!nxNodes) return 2
            if (visited[node] && nxNodes.length===1) return 1
            if (nxNodes.length===2) return 3
            visited[node] = true
            node = nxNodes[0]
        }
    }
    
    //중심노드 찾기 (들어오는 노드가 없고 나가는 노드가 2개 이상)
    const mainNode = [...outGraph].find(([node,ary]) => ary.length>1 && !inGraph.has(node))[0]
    //중심노드에서 뻗은 그래프의 종류 파악
    const ret = [mainNode,0,0,0]
    for (const nxNode of outGraph.get(mainNode)){
        ret[checkGraphType(nxNode,outGraph,visited)] ++
    }
    return ret
    
}