[Tree/Graph] 자료구조/알고리즘 구현하기
05_[Tree] 구현
Implementation Tree
Tree 구현을 위한 기본적인 코드가 작성되어 있습니다. Tree 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.
멤버 변수
입력 데이터를 담을 수 있는 value
하위 노드를 저장할 수 있는 Array 타입의 children
메서드
insertNode(value): 입력받은 value를 Tree에 계층적으로 추가할 수 있어야 합니다.
contains(value): 트리에 포함된 데이터를 찾을 수 있어야 합니다.
주의 사항
value는 어떠한 값도 들어갈 수 있지만 현재 구현하는 Tree는 숫자로 제한합니다.
사용 예시
const rootNode = new Tree(null);
for(let i = 0; i <= 4; i++) {
if(rootNode.children[i]) {
rootNode.children[i].insertNode(i);
}
rootNode.insertNode(i);
}
rootNode; // {value: null, children: Array(5)}
rootNode.contains(5); // false
rootNode.contains(1); // true
...reference 코드
class Tree {
constructor(value) {
// constructor로 만든 객체는 트리의 Node가 됩니다.
this.value = value;
this.children = [];
}
// 트리의 삽입 메서드를 만듭니다.
insertNode(value) {
// 값이 어떤 이름으로 만들어지고 어느 위치에 붙는지 떠올리는 것이 중요합니다.
// TODO: 트리에 붙게 될 childNode를 만들고, children에 넣어야 합니다.
const childNode = new Tree(value);
this.children.push(childNode);
}
// 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
contains(value) {
// TODO: 값이 포함되어 있다면 true를 반환하세요.
// tree에서 value값을 탐색합니다.
//현재 노드의 value 값이 찾는 값과 일치한다면 return합니다.
if (this.value===value) {
return true;
}
// TODO: 값을 찾을 때까지 children 배열을 순회하며 childNode를 탐색하세요.
for(let i = 0; i < this.children.length; i++) {
if (this.children[i].contains(value)) {
return true;
}
}
// 전부 탐색했음에도 불구하고 찾지 못했다면 false를 반환합니다.
return false;
}
}06_[Graph] adjacency matrix 구현
Implementation Graph
Graph 구현을 위한 기본적인 코드가 작성되어 있습니다. Graph 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해 주세요.
멤버 변수
버텍스와 간선을 담을 Array 타입의 matrix
메서드
addVertex(): 그래프에 버텍스를 추가해야 합니다.
contains(vertex): 그래프에 해당 버텍스가 존재하는지 여부를 Boolean으로 반환해야 합니다.
addEdge(from, to): fromVertex와 toVertex 사이의 간선을 추가합니다.
hasEdge(from, to): fromVertex와 toVertex 사이의 간선이 존재하는지 여부를 Boolean으로 반환해야 합니다.
removeEdge(from, to): fromVertex와 toVertex 사이의 간선을 삭제해야 합니다.
주의사항
인접 행렬 방식으로 구현해야 합니다.
구현해야 하는 그래프는 방향 그래프입니다.
구현해야 하는 그래프는 비가중치 그래프입니다.
구현해야 하는 그래프는 이해를 돕기 위해 기존 배열의 인덱스를 정점으로 사용합니다. (0, 1, 2, ... --> 정점)
인접 행렬 그래프는 정점이 자주 삭제되는 경우에는 적합하지 않기 때문에 정점을 지우는 메소드는 생략합니다.
사용 예시
const adjMatrix = new GraphWithAdjacencyMatrix();
adjMatrix.addVertex();
adjMatrix.addVertex();
adjMatrix.addVertex();
console.log(adjMatrix.matrix);
/*
TO
0 1 2
0 [0, 0, 0],
FROM 1 [0, 0, 0],
2 [0, 0, 0]
*/
let zeroExists = adjMatrix.contains(0);
console.log(zeroExists); // true
let oneExists = adjMatrix.contains(1);
console.log(oneExists); // true
let twoExists = adjMatrix.contains(2);
console.log(twoExists); // true
adjMatrix.addEdge(0, 1);
adjMatrix.addEdge(0, 2);
adjMatrix.addEdge(1, 2);
let zeroToOneEdgeExists = adjMatrix.hasEdge(0, 1);
console.log(zeroToOneEdgeExists); // true
let zeroToTwoEdgeExists = adjMatrix.hasEdge(0, 2);
console.log(zeroToTwoEdgeExists); // true
let oneToZeroEdgeExists = adjMatrix.hasEdge(1, 0);
console.log(oneToZeroEdgeExists); // false
console.log(adjMatrix.matrix);
/*
TO
0 1 2
0 [0, 1, 1],
FROM 1 [0, 0, 1],
2 [0, 0, 0]
*/
adjMatrix.removeEdge(1, 2);
adjMatrix.removeEdge(0, 2);
let oneToTwoEdgeExists = adjMatrix.hasEdge(1, 2);
console.log(oneToTwoEdgeExists); // false
zeroToTwoEdgeExists = adjMatrix.hasEdge(0, 2);
console.log(zeroToTwoEdgeExists); // false
console.log(adjMatrix.matrix);
/*
TO
0 1 2
0 [0, 1, 0],
FROM 1 [0, 0, 0],
2 [0, 0, 0]
*/reference 코드
// directed graph (방향 그래프)
// unweighted (비가중치)
// adjacency matrix (인접 행렬)
// 이해를 돕기 위해 기존 배열의 인덱스를 정점으로 사용합니다 (0, 1, 2, ... --> 정점)
class GraphWithAdjacencyMatrix {
constructor() {
this.matrix = [];
}
addVertex() {
//버텍스를 추가합니다.
const currentLength = this.matrix.length;
for (let i = 0; i < currentLength; i++) {
this.matrix[i].push(0);
}
this.matrix.push(new Array(currentLength + 1).fill(0));
}
contains(vertex) {
//TODO: 버텍스가 있는지 확인합니다.
//버택스와 간선을 담은 matrix에 vertex(index)가 있으면 true, undefined면 false
return !!this.matrix[vertex];
}
addEdge(from, to) {
const currentLength = this.matrix.length-1;
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
//TODO: 간선을 추가할 수 없는 상황에서는 추가하지 말아야 합니다.
if (from > currentLength || to > currentLength || from < 0 || to < 0) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
//TODO: 간선을 추가해야 합니다.
this.matrix[from][to]=1;
}
hasEdge(from, to) {
//TODO: 두 버텍스 사이에 간선이 있는지 확인합니다.
return !!this.matrix[from][to]
}
removeEdge(from, to) {
const currentLength = this.matrix.length - 1;
if (from === undefined || to === undefined) {
console.log("2개의 인자가 있어야 합니다.");
return;
}
//TODO: 간선을 지울 수 없는 상황에서는 지우지 말아야 합니다.
if (from>currentLength || to>currentLength || from<0 || to<0) {
console.log("범위가 매트릭스 밖에 있습니다.");
return;
}
//TODO: 간선을 지워야 합니다.
this.matrix[from][to]=0;
}
}07_[Binary Search Tree] 구현
Implementation Binary Search Tree
Tree 구현을 위한 기본적인 코드가 작성되어 있습니다. Binary Search Tree 자료구조의 특성을 이해하고 FILL_ME_IN 을 채워 테스트를 통과해주세요.
멤버 변수
입력 데이터를 담을 수 있는 value
노드를 왼쪽에 저장할 수 있는 Array 타입의 left
노드를 오른쪽에 저장할 수 있는 Array 타입의 right
메서드
insert(value): 입력받은 value를 Binary Search에 맞게 Tree에 계층적으로 추가할 수 있어야 합니다.
contains(value): 트리에 포함된 데이터를 찾을 수 있어야 합니다.
preorder(callback): 전위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
inorder(callback): 중위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
postorder(callback): 후위 순회를 통해 트리의 모든 요소에 callback을 적용할 수 있어야 합니다.
주의사항
value는 어떠한 값도 들어갈 수 있지만 현재 구현하는 Tree는 숫자로 제한합니다.
사용 예시
const rootNode = new BinarySearchTree(10);
rootNode.insert(7);
rootNode.insert(8);
rootNode.insert(12);
rootNode.insert(11);
rootNode.left.right.value; // 8
rootNode.right.left.value; //11
let arr = [];
rootNode.preorder((value) => arr.push(value * 2));
arr; // [20, 14, 16, 24, 22]
...Reference 코드
class BinarySearchTree {
constructor(value) {
// constructor로 만든 객체는 이진 탐색 트리의 Node가 됩니다.
this.value = value;
this.left = null;
this.right = null;
}
// 이진 탐색 트리의 삽입하는 메서드를 만듭니다.
insert(value) {
// 입력값을 기준으로, 현재 노드의 값보다 크거나 작은 것에 대한 조건문이 있어야 합니다.
// 보다 작다면, Node의 왼쪽이 비어 있는지 확인 후 값을 넣습니다.
if (value < this.value) {
if (this.left === null) {
this.left = new BinarySearchTree(value);
} else {
// TODO: 비어 있지 않다면 해당 노드로 이동하여 처음부터 다시 크거나 작은 것에 대한 조건을 물어보아야 할 것입니다.
// TIP: 재귀함수를 사용합니다.
this.left.insert(value)
}
// 보다 크다면, Node의 오른쪽이 비어 있는지 확인 후 값을 넣습니다.
} else if (value > this.value) {
if (this.right === null) {
this.right = new BinarySearchTree(value);
} else {
// TODO: 비어 있지 않다면 해당 노드로 이동하여 처음부터 다시 크거나 작은 것에 대한 조건을 물어보아야 할 것입니다.
// TIP: 재귀함수를 사용합니다.
this.right.insert(value)
}
//그것도 아니라면, 입력값이 트리에 들어 있는 경우입니다.
} else {
// 아무것도 하지 않습니다.
}
}
// 앞서 구현했던 트리에 비해 이진 탐색 트리는 입력값과 트리 노드의 값의 크기를 비교하고 있습니다. 왜 그런 것일까요?
// 이진 탐색 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
contains(value) {
// TODO: 값이 포함되어 있다면 true를 반환하세요.
if (this.value===value) {
return true;
}
// 입력값을 기준으로 현재 노드의 값보다 작은지 판별하는 조건문이 있어야 합니다.
if (value < this.value) {
// TODO: 현재 노드의 왼쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
if(this.left.value===value) return true;
// TODO:일치하지 않다면 왼쪽 노드로 이동하여 다시 탐색합니다.
else this.left.contains(value);
}
// 입력값을 기준으로 현재 노드의 값보다 큰지 판별하는 조건문이 있어야 합니다.
if (value > this.value) {
// TODO: 현재 노드의 오른쪽이 비어 있지 않고, 노드의 값이 입력값과 일치하면 true를 반환합니다.
// TODO:일치하지 않다면 오른쪽 노드로 이동하여 다시 탐색합니다.
return !!(this.right && this.right.contains(value)); //둘다 true라면 true를 반환
}
// 없다면 false를 반환합니다.
return false;
}
/*
트리의 순회에 대해 구현을 합니다.
지금 만드려고 하는 이 순회 메서드는 단지 순회만 하는 것이 아닌, 함수를 매개변수로 받아 콜백 함수에 값을 적용시킨 것을 순회해야 합니다.
전위 순회를 통해 어떻게 탐색하는지 이해를 한다면 중위와 후위 순회는 쉽게 다가올 것입니다.
*/
// 이진 탐색 트리를 전위 순회하는 메서드를 만듭니다.
preorder(callback) {
callback(this.value); //루트를 먼저 검색
if (this.left) {
this.left.preorder(callback);
};
if (this.right) {
this.right.preorder(callback);
};
}
// 이진 탐색 트리를 중위 순회하는 메서드를 만듭니다.
inorder(callback) {
//TODO: 전위 순회를 바탕으로 중위 순회를 구현하세요.
if (this.left) {
this.left.inorder(callback);
};
callback(this.value); //루트를 중간 검색
if (this.right) {
this.right.inorder(callback);
};
}
// 이진 탐색 트리를 후위 순회하는 메서드를 만듭니다.
postorder(callback) {
//TODO: 전위 순회를 바탕으로 후위 순회를 구현하세요.
if (this.left) {
this.left.postorder(callback);
};
if (this.right) {
this.right.postorder(callback);
};
callback(this.value); //루트를 마지막에 검색
}
}08_[Binary Tree] 이진트리 후위순회(postorder)
이진트리 후위순회(postorder)
문제
이진트리의 root노드를 줄 것입니다. 해당 이진트리의 후위 순회 결과를 출력하세요.
입력
인자 1 : TreeNode
TreeNode 타입으로 된 root 노드
출력
number[] 을 리턴해야 합니다.
주의 사항
이진트리 내의 노드 갯수의 범위는 0 - 100 입니다.
해당 문제를 재귀적인 해결책과 반복적인 해결책 모두를 사용해 풀어보세요.
입출력 예시
class TreeNode {
constructor(val, left, right) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
}
// 1
// \
// 2
// /
// 3
const root1 = new TreeNode(1, null, new TreeNode(2, new TreeNode(3), null));
const result1 = postOrderTraversal(root1);
console.log(result1); // [3, 2, 1]
const root2 = null;
const result2 = postOrderTraversal(root2);
console.log(result2); // []
const root3 = new TreeNode(1);
const result3 = postOrderTraversal(root3);
console.log(result3); // [1]Reference 코드
// Definition for a binary tree node.
// class TreeNode {
// constructor(val = 0, left = null, right = null) {
// this.val = val;
// this.left = left;
// this.right = right;
// }
// }
/**
* @param {TreeNode} root
* @return {number[]}
*/
const postOrderTraversal = (root) => {
//리턴값 숫자배열
let result = [];
//left -> right -> root
//트리의 node를 재귀적으로 순회해야 함
const dfs = (node) => {
//노드가 null이면 패스
if(node===null) return;
dfs(node.left);
dfs(node.right);
result.push(node.val);
}
dfs(root);//root를 넣어서 함수 실행
return result;
}
// 2. 반복문적 풀이법
// const postOrderTraversal = (root) => {
// const stack = []; //스택쌓을 배열
// const result = []; //리턴할 배열
// if (root === null) return result; //루트가 아무것도 없으면 빈배열 리턴
// stack.push(root); //루트를 스택 배열에 넣는다.
// while (stack.length) {//스택이 빈배열이 될때까지 반복(마지막 루트노트를 제거하면 종료)
// const node = stack.pop(); //루트를 제거해서 노드에 담는다.
// // 후위순회는 root노드의 값이 항상 가장 마지막에 방문되어야 하고, 그 말은 즉 출력결과에 뒷 편에 위치해야 하므로
// // 매번 root노드의 값을 출력결과의 맨 앞 부분에 넣어주게 되면 반복문을 돌면서 해당 값이 뒤로 밀리면서 출력결과의 뒷 편에 위치하게 된다.
// result.unshift(node.val);//노드의 value를 result 맨 처음에 담기
// // 후위순회이기 때문에 방문순서는 left -> right -> root이지만, 윗 줄의 코드에서 매번 root노드의 값을 출력결과 배열의 맨 앞에 넣어주면서 해당 값을 뒤로 밀어내고 있기 때문에
// // 다음 방문을 위한 node의 자식을 stack에 담을 때는 기존 순서대로 left -> right순으로 담아주면 된다.
// node.left && stack.push(node.left); //node.left가 있다면 스택에 node.left를 push
// node.right && stack.push(node.right);
// } //result=[루트] -> [right 루트] -> [left right 루트]
//[1] -> [2,1] -> [3,2,1]
// return result;
// };09_[Binary Tree] 이진트리 레벨순회(levelorder)
이진트리 레벨순회(levelorder)
문제
이진트리의 root노드를 줄 것입니다. 해당 이진트리의 레벨 순회 결과를 출력하세요.
입력
인자 1 : TreeNode
TreeNode 타입으로 된 root 노드
출력
number[][] 을 리턴해야 합니다.
주의 사항
이진트리 내의 노드 갯수의 범위는 0 - 2000 입니다.
입출력 예시
class TreeNode {
constructor(val, left, right) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
}
/*
3
/ \
9 20
/ \
15 7
*/
const root1 = new TreeNode(3, new TreeNode(9), new TreeNode(20, new TreeNode(15), new TreeNode(7)));
const result1 = levelOrderTraversal(root1);
console.log(result1); // [[3], [9, 20], [15, 7]];
const root2 = new TreeNode(1);
const result2 = levelOrderTraversal(root2);
console.log(result2); // [[1]]
const root3 = null;
const result3 = levelOrderTraversal(root3);
console.log(result3); // []Reference 코드
// Definition for a binary tree node.
// class TreeNode {
// constructor(val = 0, left = null, right = null) {
// this.val = val;
// this.left = left;
// this.right = right;
// }
// }
/**
* @param {TreeNode} root
* @return {number[]}
*/
const levelOrderTraversal = (root) => {
// 최종 출력결과를 반환하기 위한 배열을 만들어 줍니다.
const result = [];
// 만약 최초에 들어온 root노드 자체가 null값이라면 빈 배열을 반환하고 로직을 끝냅니다.
if (!root) return result;
// BFS를 위한 Queue를 만들어 주고, BFS시작을 위해 최초값인 root노드를 큐에 넣어줍니다.
const queue = [];
queue.push(root);
// queue에 값이 더 이상 존재하지 않을 때까지 루프를 돌며 로직을 진행시킵니다.
while (queue.length > 0) {
// 트리의 각 레벨별로 값을 묶어줘야 하기 때문에 각 레벨을 위한 내부 배열을 선언합니다.
const subResult = [];
// 해당 레벨에 존재하는 노드의 수 만큼 for 루프를 돌기 위해서 미리 큐의 사이즈를 변수에 저장합니다.
const size = queue.length;
// 해당 레벨에 존재하는 노드의 수만큼 for 루프를 돌면서 내부 배열(subResult)에 값을 추가해 갑니다.
for (let i = 0; i < size; ++i) {
// queue에서 맨 앞(head)값을 꺼내서 노드로 저장하고
const node = queue.shift(); //큐 다 없어짐
// 해당 노드의 값을 subResult 배열에 넣어줍니다.
subResult.push(node.val);
// 다음 레벨을 순회하기 위해 해당 노드에 왼쪽이나 오른쪽 자식이 있으면 큐에 삽입해 줍니다.
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
// 위의 for루프에서 해당 레벨에 해당하는 subResult 배열을 완성시킨 후 최종 반환배열인 result에 해당 subResult를 추가해 줍니다.
result.push(subResult);//[[3]] -> [[3],[9,20]] -> [[3], [9,20], [15,7]]
}
// 최종 반환배열인 result를 반환하고 로직을 끝내줍니다.
return result;
};10_[Graph] 인접 행렬 길찾기
인접 행렬 길찾기
문제
주어진 인접행렬에서 한 정점으로부터 다른 정점으로 이어지는 길이 존재하는지 반환해야 합니다.
입력
인자 1: matrix
Array 타입을 요소로 갖는 인접 행렬이 담긴 2차원 배열
인자 2: from
Number 타입의 시작 정점
인자 3: to
Number 타입의 도착 정점
출력
boolean 타입을 리턴해야 합니다.
입출력 예시
const result = getDirections(
[
[0, 1, 0, 0],
[0, 0, 1, 0],
[0, 0, 0, 1],
[0, 1, 0, 0],
],
0,
2
);
console.log(result); // true
// 정점 0에서 2로 가는 길이 존재하는지 확인합니다.
// 0 --> 1 로 가는 간선이 존재하고, 1 --> 2 로 가는 간선이 존재하기 때문에 true를 반환합니다.
const result2 = getDirections(
[
[0, 1, 0, 0, 0],
[0, 0, 0, 1, 0],
[0, 1, 0, 0, 0],
[0, 1, 1, 0, 0],
[1, 1, 1, 1, 0],
],
1,
4
);
console.log(result2); // false
// 정점 1에서 4로 가는 길이 존재하는지 확인합니다.
// 1 --> 3,
// 3 --> 1 (정점 1을 다녀왔으니 다시 돌아가지 않습니다),
// 3 --> 2,
// 2 --> 1 (정점 1을 다녀왔으니 다시 돌아가지 않습니다)
// ...으로, 4에 도달할 수 없습니다.Reference 코드
function getDirections(matrix, from, to) {
// TODO: 여기에 코드를 작성합니다.
// queue를 간단하게 생성하고, 첫 시작점으로 from을 할당합니다.
const queue = [from]; //[0]
const enqueue = (n) => queue.push(n); //뒤에 숫자 붙인다.
const dequeue = (n) => queue.shift(); //앞에 숫자 빠진다.
// 방문했다는 것을 표시하기 위해 1차원 행렬을 생성합니다.
const isVisited = new Array(matrix.length).fill(false);//[false,false,false,fasle]
// 첫 정점 방문 여부를 표시합니다.
isVisited[from] = true //[true,false,false,false]
// queue(방문할 곳)의 사이즈가 0이 될 때까지 반복합니다.
while (queue.length > 0) {
// queue에서 정점을 하나 빼서 now에 할당합니다.
const now = dequeue(); //now=0; 현재 queue=[]; -> queue=[1]에서 now=1; 현재 queue=[]; -> queue=[2]에서 now=2; 현재 queue=[];
// 목적지인지 검사하고, 목적지라면 true를 반환합니다.
if (now === to) return true; //now가 2가 되면 true
// 해당 정점의 간선들을 확인합니다.
for (let next = 0; next < matrix[now].length; next++) { //matrix의 0번째 요소의 길이까지 반복 -> 1번째 요소의 길이까지 반복
// 만약, 간선이 있고 방문하지 않았다면
if (matrix[now][next] && !isVisited[next]){ //matrix[0][1]가 1이라면 && isvisited[1]이 false라면 현재isVisited=[true,false,false,false]
// queue에 next를 넣습니다. (다음 정점으로 가기 위해) //matrix[1][2]가 1이라면 && isvisited[2]이 false라면 현재isVisited=[true,true,false,false]
enqueue(next); //queue=[1]; -> queue=[2];
// 해당 정점을 방문했다는 것을 표시합니다.
isVisited[next] = true //[true,true,false,false] -> [true,true,true,false]
}
}
}
// 길이 없다면 false를 반환합니다.
return false;
}11_[DFS / BFS] 연결된 정점들
연결된 정점들
문제
방향이 없는 간선들의 목록이 주어질 때, 연결된 정점의 컴포넌트(그룹들)가 몇 개인지 반환하는 함수를 작성하세요.
입력
인자 1: edges
2차원 Array 타입을 요소로 갖는 시작과 도착 정점이 담겨있는 배열들을 담고 있는 목록 (2차원 배열, 정수 요소)
ex) [[0, 1], [1, 2], [3, 4]]
출력
Number 타입을 리턴해야 합니다.
연결된 정점의 컴포넌트의 수를 숫자로 반환합니다.
주의 사항
주어진 간선은 무향입니다.
[1, 2] 는 정점 1에서 정점 2로도 갈 수 있으며, 정점 2에서 정점 1로도 갈 수 있습니다.
입출력 예시
const result = connectedVertices([
[0, 1],
[2, 3],
[4, 5],
]);
console.log(result); // 3
const result = connectedVertices([
[0, 1],
[2, 3],
[3, 4],
[3, 5],
]);
console.log(result); // 2
Reference 코드
function connectedVertices(edges) {
// 최대 버텍스를 찾습니다.
const maxVertex = edges.reduce((a, c) => {
const bigger = Math.max(...c);
if (bigger > a) return bigger;
return a;
}, 0);
// 이 레퍼런스는 인접 리스트로 만듭니다. (행렬도 가능합니다. 행렬로 작성해 보세요.)
const adjList = {};
// 인접 리스트에 최대 버텍스 크기만큼 반복해 버텍스를 만들어 줍니다.
for (let i = 0; i <= maxVertex; i++) {
adjList[i] = [];
}
// edges를 순회하며, (무향 그래프이므로 쌍방으로) 간선을 연결해 줍니다.
// 이렇게 adjList 그래프가 완성되었습니다.
for (let i = 0; i < edges.length; i++) {
adjList[edges[i][0]].push(edges[i][1]);
adjList[edges[i][1]].push(edges[i][0]);
}
// 방문한 버텍스를 담을 객체를 선언합니다.
const visited = {};
// 컴포넌트가 몇 개인지 카운트할 변수를 선언합니다.
let count = 0;
// 그래프에 있는 버텍스를 전부 순회합니다.
for (let vertex = 0; vertex <= maxVertex; vertex++) {
// 만약 i 번째 버텍스를 방문하지 않았다면 bfs로 해당 버텍스와, 버텍스와 연결된(간선) 모든 버텍스를 방문합니다.
// BFS로 갈 수 있는 모든 정점들을 방문하며 visited에 담기 때문에, 방문한 버텍스는 visited에 들어 있어서 bfs를 돌지 않습니다.
// 이렇게 컴포넌트를 확인합니다.
if (!visited[vertex]) {
// 그래프와 버텍스, 방문했는지 확인할 visited를 변수에 담습니다.
bfs(adjList, vertex, visited);
// 카운트를 셉니다.
count++;
}
}
// 카운트를 반환합니다.
return count;
}
// bfs solution
function bfs(adjList, vertex, visited) {
// bfs는 가장 가까운 정점부터 탐색하기 때문에 queue를 사용합니다.
// queue에 vertex를 담습니다.
const queue = [vertex];
// 해당 버텍스를 방문했기 때문에 visited에 담아 주고, 방문했다는 표시인 true를 할당합니다.
visited[vertex] = true;
// queue의 길이가 0일 때까지 순환합니다.
while (queue.length > 0) {
// cur 변수에 정점을 할당합니다.
// queue는 선입선출이기 때문에 shift 메소드를 사용하여 버텍스를 가져옵니다.
const cur = queue.shift();
// 그래프의 cur 정점에 있는 간선들을 전부 순회합니다.
for (let i = 0; i < adjList[cur].length; i++) {
// 만약, 해당 버텍스를 방문하지 않았다면 queue에 삽입합니다.
// 방문했다는 표시로 visited에 해당 버텍스를 삽입하고 true를 할당합니다.
if (!visited[adjList[cur][i]]) {
queue.push(adjList[cur][i]);
visited[adjList[cur][i]] = true;
}
// queue에 다음으로 방문할 버텍스가 있기 때문에 while은 멈추지 않습니다.
// 만약, queue가 비어 있다면 더 이상 갈 곳이 없는 것이기 때문에 bfs 함수를 종료하고 카운트를 셉니다.
}
}
}
// dfs solution
// bfs 함수 대신 dfs를 사용해도 결과는 같습니다.
function dfs(adjList, vertex, visited) {
// 해당 버텍스에 방문했다는 표시로 visited key에 vertex를 담고 값에 true를 할당합니다.
visited[vertex] = true;
// 해당 버텍스의 모든 간선들을 전부 순회합니다.
for (let i = 0; i < adjList[vertex].length; i++) {
// 만약 i번째 간선과 이어진 버텍스를 방문하지 않았다면
if (!visited[adjList[vertex][i]]) {
// dfs를 호출해(재귀) 방문합니다.
dfs(adjList, adjList[vertex][i], visited);
}
// 모든 방문이 종료되면 다음 버텍스를 확인합니다.
// 재귀가 종료되면(한 정점에서 이어진 모든 간선들을 확인했다면) dfs 함수를 종료하고 카운트를 셉니다.
}
}
// matrix
// function connectedVertices(edges) {
// // 행렬을 기준으로 하겠습니다.
// // 제일 큰 버텍스 찾기.
// const max = Math.max(...edges.flat());
// // 버텍스 찾았다면? 행렬 만들기
// const matrix = new Array(max + 1).fill(0).map(e => new Array(max + 1).fill(0));
// //엣지 넣기 ㅎㅎ
// edges.forEach(e => {
// matrix[e[0]][e[1]] = 1;
// matrix[e[1]][e[0]] = 1;
// })
// // 탐색에 가장 중요한 건? 두 번 방문하지 않는다.
// let visited = new Array(matrix.length).fill(false);
// // 카운트
// let count = 0;
// // 버텍스를 하나씩 순회하면서 연결된 정점이 있는지 확인한다!!
// for(let i = 0; i < matrix.length; i++) {
// if(visited[i] === false) {
// bfs(matrix, i, visited);
// count++;
// }
// }
// // 카운트를 반환합니다.
// return count;
// }
// // bfs solution
// function bfs(matrix, v, visited) {
// // 큐에 시작점 넣고
// let Q = [v];
// // 방문했다고 표시
// visited[v] = true;
// // 큐에 모든 게 없어질 ㄸㅐ까지 반복합니다.
// while(Q.length !== 0) {
// // 큐에서 하나 뺍니다.
// let current = Q.pop();
// // 현재 정점 확인합니다.
// for(let i = 0; i < matrix[current].length; i++) {
// // 정점 순회하면서?
// if(visited[i] !== true && matrix[current][i] === 1) {
// // 큐에 i를 넣자
// Q.unshift(i);
// // 방문했다고 표현하자
// visited[i] = true;
// }
// }
// }
// }
// // dfs solution
// // bfs 함수 대신 dfs를 사용해도 결과는 같습니다.
// function dfs(matrix, vertex, visited) {
// // 해당 버텍스에 방문 표시
// visited[vertex] = true;
// // 해당 버텍스의 모든 간선들을 전부 순회합니다.
// for (let i = 0; i < matrix[vertex].length; i++) {
// // 만약 i번째 간선과 이어진 버텍스를 방문하지 않았다면
// if(visited[i] !== true && matrix[vertex][i] === 1){
// // dfs를 호출해(재귀) 방문합니다.
// dfs(matrix, i, visited);
// }
// // 모든 방문이 종료되면 다음 버텍스를 확인합니다.
// // 재귀가 종료되면(한 정점에서 이어진 모든 간선들을 확인했다면) dfs 함수를 종료하고 카운트를 셉니다.
// }
// }
신입 프론트엔드 웹 개발자입니다.