[개발일지] - 416

여신 금액 관련 작업을 진행하다가

오후에 갑작스럽게 추가된 주문과 내부 취소 관련 복잡한 프로세스 업무를 받아버렸고

해당 업무가 이번주까지 끝나야 한다고 했기 때문에 갑작스럽게 야근을 하게 되었는데

해당 작업에 대한 기록을 따로 옮겨두지 않아서 기록이 회사에만 존재하게 되었다.

 

 

(1).백준 15681번 트리와 쿼리는 정점을 기준으로 하위 정점의 개수를 출력해야 하는 문제였는데

너무 오랜만에 트리 문제를 풀다보니 생각보다 시간이 오래 걸렸다.

 

일단 각자 접근하면서 트리를 순회해보려고 했는데

bfs 방식으로 접근하다보니 서브쿼리의 숫자를 확인할 수 없었고

결국 dfs 방식으로 변경해서 주어진 정점에 따라 점수를 부여했고

이전에 depth를 구하던 방식이 아닌 하위 노드 개수를 구해야 하는 문제였기 때문에

내부에서 다시 재귀호출로 하위의 갯수를 계속 더하는 방식으로 해결할 수 있었다.

const input = `9 5 3
1 3
4 3
5 4
5 6
6 7
2 3
9 6
6 8
5
4
8`.split('\n')

const [n, r, q] = input[0].split(' ').map(Number)
const graph = []
const sizeList = new Array(n + 1).fill(0)
const visited = new Array(n + 1).fill(false)
const results = [];

for(let i = 0 ; i <= n ; i++){
    graph.push(new Array())
}

for (let i = 1; i < n; i++) {
    const [a, b] = input[i].split(' ')
    graph[a].push(b)
    graph[b].push(a)
}

// const queue = []
// queue.push(r)

// while (queue.length > 0) {
//     let now = quque.shift()
//     visited[now] = true
//     sizeList[now] = 1

//     for(let i = 0 ; i < graph[now].length ; i++){
//         if(!visited[graph[now][i]]){
//             queue.push(graph[now][i])
//             sizeList[now]++
//         }
//     }
// }



const dfs = (node) => {
    visited[node] = true
    sizeList[node] = 1

    for (const neighbor of graph[node]) {
        if (!visited[neighbor]) {
            sizeList[node] += dfs(neighbor)
        }
    }
    return sizeList[node]
}

dfs(r)

for (let i = n; i < n + q; i++) {
    results.push(sizeList[input[i]])
}

console.log(results.join('\n'))