그래프 ( Graph )

그래프란

버텍스와 엣지로 이루어진 자료구조

버텍스 : 정점
엣지 : 버텍스를 이어주는 간선

종류

단방향 그래프

한쪽으로만 이동가능

[
	[0,1,0,0,0,1],
  	[0,0,1,0,1,0],
  	[0,0,0,1,0,0],
  	[0,0,0,0,0,0],
  	[0,0,0,0,0,0],
  	[0,0,0,0,1,0],
]

양방향 그래프

양 노드(버텍스)간 이동이 가능

[
	[0,1,0,0,0,1],
  	[1,0,1,0,1,0],
  	[0,1,0,1,0,0],
  	[0,0,1,0,0,0],
  	[0,1,0,0,0,1],
  	[1,0,0,0,1,0],
]

가중치 그래프

이동에 가중치 값이 포함됨

[
	[0,2,0,0,0,5],
  	[0,0,3,0,6,0],
  	[0,0,0,3,0,0],
  	[0,0,0,0,0,0],
  	[0,0,0,0,0,0],
  	[0,0,0,0,1,0],
]

기본 문제

DFS활용

function solution(n, arr) {
        let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0));
        let checkArr = Array.from(Array(n + 1)).fill(0);
        for (let i = 0; i < arr.length; i++) {
          graph[arr[i][0]][arr[i][1]] = 1;
        }
        let route = [];
        let result = [];
        let count = 0;
        console.log(graph);
        function dfs(v) {
          if (v === n) {
            // result = [...result, route];
            console.log(route);
            count++;
          } else {
            graph[v].forEach((el, idx) => {
              if (el === 1 && checkArr[idx] === 0) {
                checkArr[idx] = 1;
                route.push(idx);
                dfs(idx);
                checkArr[idx] = 0;
                route.pop(idx);
              }
            });
          }
          return count;
        }
        checkArr[1] = 1;
        route.push(1);
        return dfs(1);
      }

      let arr = [
        [1, 2],
        [1, 3],
        [1, 4],
        [2, 1],
        [2, 3],
        [2, 5],
        [3, 4],
        [4, 2],
        [4, 5],
      ];
      console.log(solution(5, arr));