백준 2458: 키 순서 - javascript(dfs)

문제 출처 

https://www.acmicpc.net/problem/2458

 

정답 풀이

순위를 확신할 수 있는 학생은

자기보다 작은 학생 수 + 자기보다 큰 학생 수에서  -1 한 값이 n과 같은 학생이다. 

 

+

총 학생 수가 6명일 때 

나보다 작은 학생이 3명이고, 나보다 큰 학생이 2명이면 나는 4번째 순서라는 것을 알 수 있음 

 

dfs 탐색을 통해서 나보다 몇명이 큰지 계산하고, 

나보다 작은 학생이 몇명인지 계산한다. 

 

그 후, 그 합에서 -1 한 값이 n과 같으면 answer+= 1 을 한다. ! 

정답 코드 

 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 
const [n,m] = input[0].split(' ').map(v => +v); 

const tall_list = Array.from({length: n+1}, () => [])
const small_list = Array.from({length: n+1}, () => [])

for(let i=1; i<=m; i++){
    const [a,b] = input[i].split(' ').map(v => +v)
    tall_list[a].push(b)
    small_list[b].push(a)
}

function dfs(graph,start, visited){
    let count = 0; 
    visited[start] = true;
    
    for(let next of graph[start]){
        if(!visited[next]){
           count += 1 + dfs(graph, next, visited)
        }
    }
    return count; 
}

let answer =0
for(let i=1; i<=n; i++){
    const visited_tall = new Array(n+1).fill(false)
    const visited_small = new Array(n+1).fill(false)
    
    const tall_cnt = dfs(tall_list, i, visited_tall)
    const small_cnt = dfs(small_list, i, visited_small)
    
    if(tall_cnt + small_cnt === n-1) answer++; 
}

console.log(answer)