백준 10159 : 저울 - javascript(dfs)

문제 출처 

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

 

정답 풀이 

cnt1 = 해당 물건 보다 큰 물건의 개수를 센다. 

cnt2 = 해당 물건 보다 작은 물건의 개수를 센다. 

답 = 전체 물건 개수 - cnt1 - cnt2 - 1(자기 자신)

 

개수를 세는 것은 dfs 탐색을 활용한다. 

정답 코드 

 

//무게 다른 물건 
//1부터 N 번호 
//각 물건에 대해서 그 물건과의 비교 결과를 알 수 없는 물건 개수 출력 

//각 관계들을 2차 배열로 생성 및 정리 
//dfs로 탐색 
//각 숫자로 접근해서 cnt 하기 

let input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const n = Number(input.shift())
const m = Number(input.shift())
input = input.map(el => el.split(' ').map(v => +v))

let parent = Array.from({length: n+1}, () => [])
let child = Array.from({length: n+1}, () => [])
for(let i=0; i<m; i++){
    const [a,b] = input[i]
    parent[b].push(a); 
    child[a].push(b)
}

function upperdfs(node, visited, cnt){
    visited[node] = true; 
    
    for(let i=0; i<parent[node].length; i++){
        let next = parent[node][i]; 
        if(!visited[next]){
            cnt++; 
            cnt = upperdfs(next, visited, cnt)
        }
    }
  
    return cnt; 
}

function lowerdfs(node, visited, cnt){
    visited[node] = true; 
    
    for(let i=0; i<child[node].length; i++){
        let next = child[node][i]; 
        if(!visited[next]){
            cnt++; 
            cnt = lowerdfs(next, visited, cnt)
        }
    }
  
    return cnt; 
}

for(let k=1; k<=n; k++){
    const visited = new Array(n+1).fill(false)
    let cnt1 = upperdfs(k, visited, 0)
    let cnt2 = lowerdfs(k, visited, 0)
    console.log(n-cnt1 - cnt2 - 1)
}

 

추가 설명 (cnt = dfs() 에 대하여)

1. js의 함수 호출 시 값이 어떻게 전달되는가? 

- js에서 함수에 인자를 넘길 때, 기본적으로 원시타입인 숫자, 문자열, 불리언 등은 값에 의한 전달이 이루어진다. 

즉, 함수 내부에서 인자로 전달된 값은 복사된 값이기 때문에 

해당 값을 변경해도 원래 값에 영향을 미치지 않는다. 

 

따라서, cnt를 인자로 넘겨주었을 때, 

dfs 함수 내에서 cnt++로 값을 증가시켜도 그 변화는 호출된 함수 내에서만 적용되고, 

호출한 함수에 반영되지 않는다. 

즉, 새로운 재귀 호출에서의 변화가 외부로 반영되지 않는다. 

 

함수 dfs가 호출될 때마다 새로 계산된 cnt 값을 반환하고, 

그 값을 다시 받아서 갱신해 주기 위해서 cnt = dfs()와 같은 방식으로 재귀 호출의 결과를 저장해야 한다. 

그렇지 않으면 재귀 호출 내에서의 cnt 변화는 함수의 결과에 반영되지 않는다. 

 

cnt = dfs() 와 같은 방식의 재귀 호출을 통해 cnt가 제대로 누적되면, 

함수가 최종적으로 계산된 cnt 값을 얻을 수 있다. 

간단히 말하면, 함수에 전달된 cnt는 원시값으로 전달되기 때문에 

변화된 값을 받아오려면 그 결과를 반환받아 외부에서 갱신해야 한다. 

 

 

2. 스택 프레임

개념: 

함수가 호출될 때마다 새로운 스택 프레임이 생성된다. 

이 스택 프레임은 함수의 매개변수와 지역변수를 저장하는 공간이다. 

각 함수 호출은 독립적인 스택 프레임을 가지고 있기 때문에, 

함수 안에서 사용되는 변수들이 서로 영향을 주지 않고 각 호출마다 따로 관리된다. 

 

재귀 함수에서 스택 프레임 작동방식 

 

1) 함수 호출 

dfs(node, visited, cnt, parent) 함수가 호출될 때, 새로운 스택 프레임이 생성된다. 

이 스택 프레임에는 ndoe, visited, cnt, parent 값이 저장된다. 

 

2) 재귀 호출 

- 함수가 다시 자기 자신을 호출하는 재귀 함수의 경우, 또 하나의 새로운 스택 프레임이 생성된다. 

이 전에 사용한 변수들은 새로운 스택 프레임에서 복사된 값으로 전달된다. 

 

- 예를 들어, cnt가 3일때 재귀 호출이 일어나면, 새로운 스택 프레임에서는 cnt=3으로 시작된다. 

이 값이 함수 내에서 변화해도 이전 스택 프레임의 cnt 값에는 영향을 미치지 않는다. 

 

3) 값 변화 

- 재귀 호출 안에서 cnt++로 cnt가 증가되면, 그 변화는 해당 스택 프레임 안에서만 적용된다. 

즉, 현재 함수 호출의 스택 프레임에서만 cnt가 증가하고, 

그 값은 다른 스택 프레임에는 영향을 미치지 않는다. 

 

4) 재귀가 끝나고 반환

- 재귀 호출이 끝나면, 마지막으로 호출된 함수가 먼저 종료된다. 이때 cnt가 반환되며,

이 값을 이전 스택 프레임에서 받아야 한다. 

이 과정을 통해 각 재귀 호출에서 cnt 값을 반환하고, 

이를 상위 함수에서 받아서 다시 갱신한다. 

 

5) 스택 프레임 해제 

- 함수가 종료되면 해당 스택 프레임은 사라지고, 이전에 존재하던 스택 프레임이 다시 활성화된다. 

그러면서 반환된 값을 받아서 사용할 수 있게 되는 것이다. 

 

결론) 

재귀 호출에서 cnt가 증가한 값을 상위 함수로 전달하기 위해 cnt = dfs()로 반환된 값을 받아야 ㅎ나다. 

각 호출의 cnt 값은 별도의 스택 프레임에 존재하기 때문에, 

반환된 값을 받아서 갱신하지 않으면 변경된 값을 반영할 수 없다.