[JS] 순위

DFS + 그리디 알고리즘을 활용해서 해결해보았다.

 

우선 그래프 두개를 두고

 

a > b라면

winGraph와 loseGraph를 두고 이긴쪽,진쪽만 저장했다.

 

이후 n번째 노드가 들어왔다면 해당 노드를 이긴사람들을 차례로 탐색했다. 또 진쪽으로도 마찬가지로 한방향만을 탐색했다.

 

이렇게 한 이유는 순위를 정확히 매기려면 a>b>c ... 이렇게 한 방향이 고정적으로 되어있어야 하기 때문이다.

 

 

 

 

++ DP를 사용해서 저장한다면 조금 더 효율적인 코드를 짜는것도 가능할 듯 하다.

 

 

function solution(n, results) {
    const winGraph = [...new Array(n+1)].map(_ => [])
    const loseGraph = [...new Array(n+1)].map(_ => [])
    
    for (const [a,b] of results){
        winGraph[a].push(b)
        loseGraph[b].push(a)
    }
    
    const getLinkedGraphSize = (node,graph,visited) => {
        if(visited[node]) return 0
        visited[node] = true
        let ret = 1
        for (const nxNode of graph[node])
            ret += getLinkedGraphSize(nxNode,graph,visited)
        return ret
    }
    
    let ret = 0
    for (let i = 1 ; i <= n ; i++){
        let cnt = 0
        let visited = Array(n+1).fill(false)
        cnt += getLinkedGraphSize(i,winGraph,visited)
        visited = Array(n+1).fill(false)
        cnt += getLinkedGraphSize(i,loseGraph,visited)
        if (cnt===n+1) ret ++
    }
    return ret
}