노션에서 마이그레이션 중이며, 순서는 랜덤하게 업로드하고 있습니다.
해당 문제는 코드스테이츠의 Toy problem을 출처로 합니다.
2022.04.01
문제
임의의 tree를 구성하는 노드 중 하나의 Node 객체를 입력받아, 해당 노드를 시작으로 깊이 우선 탐색(DFS, Depth First Search)을 합니다. 이 때, 탐색되는 순서대로 노드의 값이 저장된 배열을 리턴해야 합니다.
입력
인자 1 : node
- 'value', 'children' 속성을 갖는 객체 (Node)
- 'node.value'는 number 타입
- 'node.children'은 Node를 요소로 갖는 배열
출력
- 배열을 리턴해야 합니다.
주의사항
- 생성자 함수(Node)와 메소드(addChild)는 변경하지 않아야 합니다.
입출력 예시
let root = new Node(1);
let rootChild1 = root.addChild(new Node(2));
let rootChild2 = root.addChild(new Node(3));
let leaf1 = rootChild1.addChild(new Node(4));
let leaf2 = rootChild1.addChild(new Node(5));
let output = dfs(root);
console.log(output); // --> [1, 2, 4, 5, 3]
leaf1.addChild(new Node(6));
rootChild2.addChild(new Node(7));
output = dfs(root);
console.log(output); // --> [1, 2, 4, 6, 5, 3, 7]
알고리즘
작성 코드 / 레퍼런스 코드
let dfs = function (node) {
// TODO: 여기에 코드를 작성합니다.
let values = [node.value];
node.children.forEach((n) => {
values = values.concat(dfs(n));
})
return values;
};
// 이 아래 코드는 변경하지 않아도 됩니다. 자유롭게 참고하세요.
let Node = function (value) {
this.value = value;
this.children = [];
};
// 위 Node 객체로 구성되는 트리는 매우 단순한 형태의 트리입니다.
// membership check(중복 확인)를 따로 하지 않습니다.
Node.prototype.addChild = function (child) {
this.children.push(child);
return child;
};
'Problem Solving' 카테고리의 다른 글
[SWEA] D3 - 13547. 팔씨름 in 파이썬 (0) | 2022.05.22 |
---|---|
[SWEA] D3 - 13229. 일요일 in 파이썬 (0) | 2022.05.22 |
[SWEA] D2 - 1859. 백만 장자 프로젝트 in 파이썬 (0) | 2022.05.19 |
[SWEA] D2 - 1984. 중간 평균값 구하기 in 파이썬 (0) | 2022.05.19 |
[SWEA] D2 - 1986. 지그재그 숫자 in 파이썬 (0) | 2022.05.19 |