👨‍💻
자료구조의 또 다른 형태로는 Graph가 있다.
근데 이번에도 컴퓨터 세계에서 말하는 그래프는 내가 아는 그래프가 아니었다.
x축 y축으로 만들어진 그래프가 아니라 네트워크 망처럼 얽히고 얽힌 그래프를 말하는듯 하다.


컴퓨터 나라의 언어로는 저 Node를 Vertex라고 하고
이어진 선을 Edge라고 한다.


아래는 Graph구조 알고리즘 문제들이고 주석으로 설명을 닳아놨다.
언제쯤 주석없이 빠르게 코드들을 이해할 수 있을까

🖇Implementation Graph

class GraphWithAdjacencyMatrix {
  // <graph의 constructor를 구현합니다.>
  constructor() {
    this.matrix = [];
  }
  
  // <vertex를 추가하는 기능을 만듭니다.> 근데 생각해야 할 것이 우리는 빈 배열에 addVertax라는 method를 통해 하나씩 node를 추가해 가는 것이다. 처음부터 5개의 노드를 만들겠다는 불가능하다.
  addVertex() {
    const currentLength = this.matrix.length;
    for (let i = 0; i < currentLength; i++) {
      this.matrix[i].push(0);
    } // 만약 this.matrix.length가 3이라면 matrix첫번재 행으로 000을 넣는다
    this.matrix.push(new Array(currentLength + 1).fill(0));
    //방금 만든 배열을 new Array(length인자)를 통해 length인자 만큼의 길이를 가지는 array를 생성한다. 그리고 거기를 fill을 통해 0이라는 하나의 값으로 채워넣는다.
    //여기서 currentLength + 1을 해준 이유는 빈배열[]로 시작할 때 for문을 거치지 않고 내려오는 경우(currentLength = 0 경우) 빈배열에 배열을 추가해주기 위해 적어줌 만약 여기로 처음 내려온다면은 [0]으로 return될거임 
  }

  // <vertex를 탐색하는 기능을 만듭니다.>
  //this.matrix에 vertex가 존재한다면 true를 리턴하고, 반대의 경우라면 false를 리턴합니다.
  contains(vertex) {
    return !!this.matrix[vertex];
  } // *** 느낌표 두개(!!)는 undefined, "", 0 값은 false, 그 외에는 true값을 return한다.

  // <vertex와 vertex를 이어주는 edge를 추가하는 기능을 만듭니다.>
  addEdge(from, to) {
    const currentLength = this.matrix.length - 1;
    // 두 가지 인자 중, 어느 하나라도 undefined라면, 리턴합니다.
    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }
    // from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면, 리턴합니다.
    if (
      from > currentLength ||
      to > currentLength ||
      from < 0 ||
      to < 0
    ) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }
    // this.matrix[from][to]의 값을 1로 바꿔줘서 edge로 연결이 되어 있음을 표시합니다.
    this.matrix[from][to] = 1;
  } // *** 2차원 배열을 생성할 때 board[4][4]와 같은 문법을 사용할 수 있다. 4행 4열이라는 뜻이다.

  // <from vertex와 to vertex 사이에 edge를 가지고 있는지 여부를 판단하는 기능을 만듭니다>
  hasEdge(from, to) {
    return !!this.matrix[from][to];
  }

  // <from vertex와 to vertex 사이에 관련이 없다면, edge를 제거 하는 기능을 만듭니다.>
  removeEdge(from, to) {
    const currentLength = this.matrix.length - 1;
    // 두 가지 인자 중, 어느 하나라도 undefined라면, 리턴합니다.
    if (from === undefined || to === undefined) {
      console.log("2개의 인자가 있어야 합니다.");
      return;
    }

    // from vertex와 to vertex가 전체 그래프의 범위를 벗어난다면, 리턴합니다.
    if (
      from > currentLength ||
      to > currentLength ||
      from < 0 ||
      to < 0
    ) {
      console.log("범위가 매트릭스 밖에 있습니다.");
      return;
    }

    // this.matrix[from][to]의 값을 0으로 바꿔줘서 관련이 없음을 표시합니다.
    this.matrix[from][to] = 0;
  }
}

사용 예시

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]
*/

1️⃣0️⃣1️⃣0️⃣0️⃣ 인접 행렬 생성하기

function createMatrix(edges) {
	// [몇 곱하기 몇 행렬을 적어줄지 생각하기 위해 인자로 받는 edges의 행렬에 최댓값을 구한다.] 
	// max 변수를 0으로 할당하고, edges(number type의 배열)를 전부 순회해 제일 큰 숫자를 max에 할당합니다.
	// max보다 크지 않을 경우엔 바꾸지 않습니다.
	let max = 0;
	for (let i = 0; i < edges.length; i++) {
		const curMax = Math.max(...edges[i].slice(0, 2));
		curMax > max ? (max = curMax) : null;
	} // *** Math.max는 입력받은 숫자 중 가장 큰 값을 반환한다.
		// *** slice는 [0, 3, "directed"]에서 "directed"를 제거하기 위해 적혀졌다.
		// *** 삼항연산자 -> 조건문 ? 선택문 1(조건문이 true일 때) : 선택문 2(조건문이 false일 때)

  // [matrix의 뼈대를 잡는다.]
  // max로 구한 최대값에 1을 더하여 array를 만들고(0번째부터 있기 때문입니다) 전부 0으로 채운 뒤(초기값을 만들고 있기 때문임)
	// map을 사용해 각 요소마다 배열로 바꿔줍니다. 배열의 크기를 이번에도 최대값에 1을 더한 뒤, 0으로 채웁니다.
  // 이 줄은 외우는게 빠름
	const result = new Array(max + 1).fill(0).map(function(el) { //여기까지 [0, 0, 0]이런 형태다가 3개의 요소에 map을 통해 배열을 채워줌으로써 행렬 형태로 바뀜
		return new Array(max + 1).fill(0);
	});
	
	// !!! new Array(max + 1).fill(new Array(max + 1))처럼 하게 되면, 주소를 참조하게 됩니다. 꼭 0을 채운 뒤, Map으로 바꾸는 등
	// 주소를 참조하지 않는 방법을 사용해야 합니다 !!!

	// [directed와 undirected를 구별하여 1을 채워주자.]
  // edges를 순회하며 무향인 곳엔 각각의 간선에 1로 바꾸어 주고, 방향이 있는 간선엔 해당 간선에만 1로 바꾸어 줍니다.
	// 만약, [0, 3, "directed"]가 들어왔다면,
	// 만들어 둔 result의 0 번째 row, 4 번째 col에 1을 추가합니다.
	// [ 0, 0, 0, 1 ] => 이렇게 될것임
	edges.forEach(function(el) {
		const [row, col, direction] = edge;
		if (direction === "undirected") {
			result[col][row] = 1;
		}
		result[row][col] = 1;
	});
	// *** forEach는 배열 method로서 map과 유사한 기능을 하는데 가장 큰 차이점은 forEach는 따로 배열을 반환하지 않는다는 점이다(그저 단순 callback함수의 반복만 이뤄진다).

  // result를 반환합니다.
	return result;
}

//[수도코드] : 방향성을 들고 있는 인접행렬 생성하기
// 1. matrix의 틀을 먼저 잡아준다. -> 전달받은 edges의 배열을 순회하며 가장 큰 값을 찾고 이 값을 기준으로 matrix틀을 만든다.
// 2. directed와 undirected를 구별해 matrix에 표현한다.

입출력 예시

const output1 = createMatrix([
	[0, 3, "directed"],
	[0, 2, "directed"],
	[1, 3, "directed"],
	[2, 1, "directed"],
]);

console.log(output1);
/**
 * [
 *  [0, 0, 1, 1],
 *  [0, 0, 0, 1],
 *  [0, 1, 0, 0],
 *  [0, 0, 0, 0]
 * ]
 */

const output2 = createMatrix([
	[0, 2, "directed"],
	[2, 4, "undirected"],
	[1, 3, "undirected"],
	[2, 1, "directed"],
]);

console.log(output2);
/**
 * [
 *  [0, 0, 1, 0, 0],
 *  [0, 0, 0, 1, 0],
 *  [0, 1, 0, 0, 1],
 *  [0, 1, 0, 0, 0],
 *  [0, 0, 1, 0, 0],
 * ]
 */

🛣인접 행렬 길찾기

function getDirections(matrix, from, to) {
	
	// [길을 찾는 일을 할 것임으로, 우리는 방문할 곳과 방문한 곳에 대한 storage가 필요하다 그래서 queue를 만들어준다(차례대로 넣고 빼주는데 용이함).]
  const queue = [from];
  const enqueue = (n) => queue.push(n);
  const dequeue = (n) => queue.shift(); // dequeue는 따로 인자 필요없이 배열의 첫번째 요소를 제거한다.
	// *** push는 배열 method로서 배열의 끝에 요소를 추가한다.
	// *** shift는 배열 method로서 배열의 첫번째 요소를 제거한다. (pop은 마지막 요소를 제거함, 주로 stack에서 쓰일듯)

	// [길을 찾을 때 중복된 vertax를 방문할 수 없음으로 발자국을 남기기 위해 방문표시를 남겨준다.]
  // 방문표시를 위해 isVisited로 표시된 vertax의 row는 모두 false로 채워줄거임
  const isVisited = new Array(matrix.length).fill(false);

  // 첫 정점 방문 여부를 표시합니다. false 2차원 행렬로 채워져있는 상태에서 선택된 정점 배열의 모든 인자를 true로 바꿔준다(0,1 로 보이는 배열과 달리 새로운 배열을 따로 만들어서 true로 채워줌).
  isVisited[from] = true

	// [while문을 통해 from을 기준으로 from vertax에 연결된 edges를 찾으며 이동한다. 만약 목적지 to를 찾으면 true를 return한다.]
  // queue(방문할 곳)배열의 길이가(length) 남아있을 때까지(0이 될 때까지) 반복합니다.
  while (queue.length > 0) {

    // queue(방문할 곳)에서 정점(vertax)을 하나 빼서 now에 할당합니다.
    const now = dequeue();

    // 목적지인지 검사하고, 목적지라면 true를 반환합니다.
    if (now === to) return true;

    // 해당 정점의 간선들을 확인합니다.
    for (let next = 0; next < matrix[now].length; next++) {
      // 만약, 간선이 있고 방문하지 않았다면
      if (matrix[now][next] && !isVisited[next]){
				// 배열에 간선(1)이 있고, isVisited의 요소가 false이면 queue에 next를 넣습니다. (다음 정점으로 가기 위해)
        enqueue(next);
        // 해당 정점을 방문했다는 것을 표시합니다.
        isVisited[next] = true
      }
    }
    
  }

  // 길이 없다면 false를 반환합니다.
  return false;
}

// [수도코드] : 2차원 인접행렬의 from to 이동경로 찾기
// 1. from을 기준으로 길을 찾을 때 우리가 지금 어느 위치에 있고 어디로 갈지에 대한 저장공간을 만든다.
// 2. 길을 찾을 때 중복된 vertax는 방문할 수 없음으로 new Array를 만들어 visited에 대한 true, false를 구분짓는다.
// 3. from을 기준으로 row 배열의 요소들을 순회하며 어느 vertax와 edges로 연결되어있는지 확인한다. 그리고 확인되면 연결되어 있는 vertax로 이동하여 목적지 to와 일치되는 점이 있는지 반복해서 찾는다.

입출력 예시

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에 도달할 수 없습니다.

👨‍💻
Tree자료구조의 시각적인 모형은 크리스마스 트리를 생각하면 편할 듯 하다.
Root라고하는 하나의 꼭짓점 데이터를 시작으로 여러 데이터가 edges로 연결되어 있다는 것이 특징이다.


가장 대표적인 예제로는 컴퓨터의 디렉토리 구조를 생각하면 된다.
폴더 안에 폴더에 진입하고 다시 또 폴더에 진입하고 하는 것을 생각하면 이해가 쉽다.

🌲Implementation Tree

class Tree {
  constructor(value) {
		// constructor로 만든 객체는 트리의 Node가 됩니다.
    this.value = value;
    this.children = [];
  }

	// 트리의 삽입 메서드를 만듭니다.
  insertNode(value) {
		// 값이 어떤 이름으로 만들어지고 어느 위치에 붙는지 떠올리는 것이 중요합니다.
    const childNode = new Tree(value);
    this.children.push(childNode);
  }

	// 트리 안에 해당 값이 포함되어 있는지 확인하는 메서드를 만듭니다.
  contains(value) {
    if (this.value === value) {
      return true;
    }
    
  
    for (let i = 0; i < this.children.length; i += 1) {
      const childNode = this.children[i];
      if (childNode.contains(value)) {
        return true;
      }
    }
		// 전부 탐색했음에도 불구하고 찾지 못했다면 false를 반환합니다.
    return false;
  }
}

사용예시

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
...

아~ 머리야~