Graph - adjacency matrix 생성

인접 행렬 생성하기

문제
Number 타입의 방향/무향인 간선들의 목록이 담긴 배열을 받아,
2차원 배열의 인접행렬을 반환하는 함수를 작성하세요.

조건
각 간선은 3가지 정보를 담고 있습니다.
0번째: 간선의 시작 정점 (0 이상의 정수)
1번째: 간선의 도착 정점 (0 이상의 정수)
2번째: 방향성 ('undirected' 무향, 'directed' 방향)
입력
인자 1: edges
Number 타입의 방향/무향인 간선들의 목록이 담긴 배열
출력
Array 타입을 리턴해야 합니다.
2차원 배열의 인접 행렬

풀이 1

function createMatrix(edges) {

  // 1. 정점 중 제일 큰 값 찾기
  // - edges 배열을 순회하면서 가장 큰 수를 찾는다.
  
  let maxNum = 0; // 찾을 최댓값 임의 설정
  for (let edge of edges) {
    let edgeMax = Math.max(...edge.slice(0, 2)); 
    // 요소 edge 배열의 최댓값인 edgeMax
    // 비교 가능한 숫자로만 구성해 
    // 전개구문을 이용해 Math.max의 인자로 넣어줬다.
    maxNum < edgeMax ? (maxNum = edgeMax) : null;
  }

  // 2. maxNum을 통해 인접 정렬 틀 만들기 
  // ❗️ 중요포인트는 주소가 참조되는 얕은 복사가 되지 않도록하는 것!
  
   let matrix = []
   for(let i = 0; i < maxNum + 1; i++) {
     matrix.push(new Array(maxNum + 1).fill(0))
   } // maxNum + 1? 배열은 0번째부터 있으니까!
      

  // 3. 정점에 간선 추가하기
  // edges 배열을 순회하면서 조건 edge[2]에 맞게 간선 추가

  for(let edge of edges) {
      if (edge[2] === "undirected") {
	matrix[edge[1]][edge[0]] = 1;
      }
    matrix[edge[0]][edge[1]] = 1;
  } // 무방향이면 시작과 도착을 뒤집은 것도 1로 변경해주고
    // 나머지는 그 방향만 1로 변경한다.
 return matrix;
}

풀이 2

배열 메소드를 통해 더욱 간결하게 풀어봤다.

function createMatrix(edges) {

  // 1. 정점 중 제일 큰 값 찾기
  let maxNum = Math.max(...edges.flat()
                      .filter(el => typeof el === 'number'))
  
  // 2. 인접 정렬 틀 만들기
  // ❗️ 중요 포인트는 얕은 복사가 되지 않도록하는 것!
  // 깊은 복사를 위해 전개구문, new Array 메소드를 이용했다.
  
  // 2-1 map method
  const matrix = new Array(maxNum + 1).fill(0).map(el => 
  			new Array(maxNum + 1).fill(0));
  
  // 2-2. reduce method
  let maxArr = new Array(maxNum + 1).fill(0)
  let matrix = [...maxArr].reduce((acc, cur) => {
    		  acc.push([...maxArr])
    		  return acc;
  		}, []); 
            
  // 3. 정점에 간선 추가하기
  edges.forEach((edge) => { 
        // 배열구조분해 -> 변수할당
	const [from, to, direction] = edge; 
	if (direction === "undirected") {
		matrix[to][from] = 1;
	}
       matrix[from][to] = 1;
   });
  
 return matrix;
}

TIL Point

• flat()
  주어진 depth만큼 배열을 까준다.
  그리고 빈 공간을 메어주기도 한다!

const newArr = arr.flat(depth)
const hasHole = [1, 2, , 4, 5];
hasHole.flat(); // [1, 2, 4, 5]

• slice()

arr.slice(begin, end)

배열의 begin부터 end 전까지를 얕은 복사본으로 추출해 새로운 배열 객체로 반환한다.
원본 배열은 바뀌지 않으나 객채 참조의 경우는 둘 다 변경된다.

• 얕은 복사 vs 깊은 복사
  깊은 복사는 내용이 같은 다른 배열을 만드는 것이고,
  얕은 복사는 해당 배열을 참조하는 주소값을 할당해 주는 것이다.
  얕은 복사를 피하기 위한 방법은 여러가지가 있겠지만,
  new Array 메소드로 새 배열을 만들어 할당 해주는 방법과,
  [...변수명]과 같은 spread syntax를 사용한 방법이 있다.
• null vs undefined
  undefined은 함수가 값을 반환하지 않을 때, 변수가 값을 할당받지 않았을 때 보인다.
  null은 어떤 값이 의도적으로 비어있음을 표현할 때 사용한다.

// 정의되지 않고 초기화된 적도 없는 경우
foo; //ReferenceError: foo is not defined
// 존재하지만 값이나 자료형이 존재하지 않는 경우
let foo = null;
foo; //null

• 배열 구조 분해 '변수할당'
  변수에 담으면 변수명 덕분에 요소가 헷갈리지 않아 로직에 방해받지 않는다!

const [from, to, direction] = edge;
/* let from = edge[0];
   let to = edge[1];
   let direction = edge[2]; */