[JS] 동굴탐험 (2020 카카오인턴십)

어렵고 까다로운 그래프 문제였다.

 

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

프로그래머스

 

문제부터가 길고 복잡하기에 문제를 간략화할 필요가 있다.

 

결국 문제의 핵심은 "모든 노드를 방문할 수 있는가?"이다.

 

또다른 핵심은 A->B처럼 B노드에 방문하기 위해 A를 먼저 방문해야 하는 경우가 있지만 "중첩되지 않는다" 가 중요 포인트이다. 즉 특정 노드 N은 아무것도 아니거나, 방문하기 위해 선방문해야하거나, 후방문 해야한다.

 

 

문제를 해결한 방법을 설명하기 전에 선언한 변수와 그 역할들을 설명하고 가려고 한다. (예시는 1번 테케 대상이다!)

 

1. tmpGraph : 양방향 그래프의 정보를 모두 등록, 그래프의 기준은 0으로 둔다.

[
  [ 1, 7, 3 ], [ 8, 0, 2 ],
  [ 1 ],       [ 0, 6 ],
  [ 7 ],       [ 7 ],
  [ 3 ],       [ 0, 4, 5 ],
  [ 1 ]
]

 

2. graph : 그래프의 자식 정보만 담겨있음 (graph[i] -> i의 자식들)

[
  Set(3) { 1, 7, 3 },
  Set(2) { 8, 2 },
  Set(0) {},
  Set(1) { 6 },
  Set(0) {},
  Set(0) {},
  Set(0) {},
  Set(2) { 4, 5 },
  Set(0) {}
]

 

3. parentInfo : 그래프의 부모 정보만 담겨있음 (parentInfo[i] -> i의 부모노드)

[
  0, 0, 1, 0, 7,
  7, 3, 0, 1
]

 

4.orderMap : order를 map으로 저장 key : end , val : start

Map(3) { 5 => 8, 7 => 6, 1 => 4 }

5.reverseOrderMap : 4번에서 key,value가 반대

Map(3) { 8 => 5, 6 => 7, 4 => 1 }

 

6. ableNode : 현재 접근이 가능한 Node들의 정보를 저장

7. stk : 새롭게 열린 Node를 검사

 

 

( 지금 생각하면 4-5번은 하나로 합쳐도 되었을 듯 )

 

 

이런 자료들을 가지고 내가 문제를 해결한 방법 자체는 간단하다.

 

0. 0번 노드를 기준으로 갈 수 있는 노드들을 stk에 넣어준다.

1. orderMap에서 현재 열려있는 노드(ableNode) 중 새롭게 갈 수 있는 노드를 stk에 넣어준다.

2. stk의 값중 마지막 값을 빼낸다. (start라하자)

3. start가 개방되면서 추가로 방문할 수 있는 노드를 reverseOrderMap에서 가져온다. (end라 하자)

4. 만약 3번을 만족하는 end가 존재한다면 end를 ableNode에 넣고 그 자식들도 방문할 수 있다면 넣어준다.

5. 만약 3번을 만족하는 end가 존재한다면 orderMap과 reverseOrderMap에서 end,start를 제거해준다.

6. 2-5번 과정을 stk가 비워질 때까지 반복한다.

7. 1-6 번 과정을 orderMap의 크기가 변함이 없는 경우까지 반복해준다.

8. 7번과정이 끝났을 때 ableNode의 개수가 N이면 전 노드의 방문이 가능하다.

 

 

 

function solution(n, path, order) {
    //그래프 등록
    const tmpGraph = [...Array(n)].map(_ => [])
    for(const [s,e] of path){
        tmpGraph[s].push(e)
        tmpGraph[e].push(s)
    }
    
    //자식,부모 정보만 가진 그래프 등록
    const graph = [...Array(n)].map(_ => new Set())
    const parentInfo = Array(n).fill(0)
    const levelInfo =  Array(n).fill(0)
    const setGraph = (node,parent,level) => {
        levelInfo[node] = level
        for(const nxNode of tmpGraph[node]){
            if(nxNode===parent) continue
            graph[node].add(nxNode)
            parentInfo[nxNode] = node
            setGraph(nxNode,node,level+1)
        }
    }
    setGraph(0,-1,0)
    
    
    
    //명령등록 : key에 접근하려면 val방문필요
    const orderMap = new Map()
    const reverseOrderMap = new Map()
    for(const [s,e] of order){
        orderMap.set(e,s)
        reverseOrderMap.set(s,e)
    }
    if(orderMap.has(0)) return false // 0이 무조건 시작점임
    
    //현재 방문 가능한 노드들
    const ableNode = new Set()
    
    //특정 node부터 방문 가능 노드를 계산
    const setAbleNode = (node) => {
        if(ableNode.has(node)) return []
        ableNode.add(node)
        const ret = [node]
        for(const nxNode of graph[node]){
            if(orderMap.has(nxNode)) continue
            ret.push(...setAbleNode(nxNode))
        }
        return ret
    }
    
    
    const stk = []
    stk.push(...setAbleNode(0)) // 초깃값 설정
    
    while(orderMap.size>0){
        //orderMap에서 갈 수 있는 노드를 새로 열어줌
        const tmpOrderMapSize = orderMap.size
        for(const [end,start] of orderMap){
            if(!(ableNode.has(start) && ableNode.has(parentInfo[end]))) continue
            orderMap.delete(end)
            stk.push(...setAbleNode(end))
        }
        //stk에는 새로 방문가능한 노드들의 정보가 담겨있고 이를 토대로 지움
        while(stk.length){
            const start = stk.pop()
            if(!reverseOrderMap.has(start)) continue
            const end = reverseOrderMap.get(start)
            if(!ableNode.has(parentInfo[end])) continue
            orderMap.delete(end)
            reverseOrderMap.delete(start)
            const addNodes = setAbleNode(end)
            for(const addNode of addNodes) stk.push(addNode)
        } 
        
        if(tmpOrderMapSize===orderMap.size) return false
    }
    
    return ableNode.size===n ? true : false
    
}