그래프와 인접행렬

🙋‍♀️그래프?

G(V vertax, E edge)
vertax(정점) : 노드, edge : 노드와 노드를 연결하는 간선, 변. 👉 정점(V)와 간선(E)으로 이루어진 집합

✏️ 무방향 그래프

각 노드가 연결되어있는 형태 (1번에서 2번으로 갈 수도 있고 2번에서 1번으로도 가능함) (양뱡향 그래프라고 보아도 된다.)
graph[a][b] =1, graph[b][a] =1

✏️ 방향 그래프

이동하는 방향이 있는 그래프 (양방향 불가)
graph[a][b] =1

✏️ 가중치 방향그래프

방향그래프에 가중치까지 있는 그래프
graph[a][b] =c(가중치) ex) graph[1][2] =2

2. 경로 탐색(인접행렬 : 노드개수가 적을 때)

🙋‍♀️인접행렬?

각 노드에 정수형의 배열 인덱스를 세팅한다. 그리고 정점 간 연결 상태는 2차원 배열의 값으로 표시하는데 배열[i][j] === 1 은 인덱스 i인 노드와 인덱스 j인 노드 사이 간선이 존재함을 의미하며, 그외에는 0이다.

문제) 방향그래프가 주어지면 1번 정점에서 N번 정점으로 가는 모든 경로의 가지 수를 출력하는 프로그램을 작성하기. 아래 그래프에서 1번 정점에서 5번 정점으로 가는 가지 수는 총 6가지이다.

  function solution(n, arr) {
    let answer = 0;
    let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0)); // 인접행렬 만들 이차원 배열 n+1인 것 유의할 것! (1번 인덱스부터 사용하므로)
    let ch = Array.from({ length: n + 1 }, () => 0);
    let path = [];
    for (let [a, b] of arr) {
      graph[a][b] = 1;
    }
    function DFS(v) {
      if (v === n) {
        answer++;
        console.log(path);
      } else {
        for (let i = 1; i <= n; i++) {
          if (graph[v][i] === 1 && ch[i] === 0) {
            // DFS(i)를 기준으로 대칭적으로 추가하는 부분, 빼는 부분이 나뉜다!
            ch[i] = 1;
            path.push(i);
            DFS(i);
            ch[i] = 0; //백하는 지점
            path.pop(); // 백하는 지점
          }
        }
      }
    }
    path.push(1);
    ch[1] = 1; // 매우중요! 1 체크 해주고 함수 실행시키기 그렇지 않으면 다시 1로 돌아오는 경로도 추가됌
    DFS(1);
    return answer;
  }

  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)); //6

👉 D(1)에서부터 이중포문 시작된다. (트리화 시키는 연습 계속 할 것)
⭐️ DFS함수를 실행시키기 전에 반드시 ch[1] =1 해주기❗️ (그렇지 않으면 다시 1로 돌아오는 경로까지 추가된다.)

3. 경로탐색(DFS-인접리스트 : 노드 개수가 많을 때 적용)

🙋‍♀️인접리스트?

인접행렬을 사용할 시, 노드의 개수가 많아지면 시간복잡도가 너무 커진다. (n의 제곱) 👉 이 경우 인접리스트를 사용한다.
✏️인접리스트? 각 노드마다 갈 수 있는 노드의 번호를 적는다. 이후 i=0 ~ g[v].length까지의 포문을 돈다. ex) 1에서는 2,3,4를 갈 수 있으므로 0~3까지 포문을 도는 것

위의 문제를 인접리스트를 활용하여 풀어보기

  function solution(n, arr) {
    let answer = 0;
    let graph = Array.from(Array(n + 1), () => Array()); //n+1행과 빈열
    let ch = Array.from({ length: n + 1 }, () => 0);
    for ([a, b] of arr) {
      graph[a].push(b);
    }

    function DFS(v) {
      if (v === n) answer++;
      else {
        for (let i = 0; i < graph[v].length; i++) {
          if (ch[graph[v][i]] === 0) {
            ch[graph[v][i]] = 1;
            DFS(graph[v][i]);
            ch[graph[v][i]] = 0; // graph[v][i] : 정점
          }
        }
      }
    }
    ch[1] = 1;
    DFS(1);

    return answer;
  }

  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));

4. 미로탐색

7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하기. 출발점은 격 자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 통로이다. 격 자판의 움직임은 상하좌우로만 움직인다.

  function solution(board) {
    let answer = 0;
    let dx = [-1, 0, 1, 0];
    let dy = [0, 1, 0, -1];
    function DFS(x, y) {
      if (x === 6 && y === 6) answer++;
      else {
        for (let k = 0; k < 4; k++) {
          let nx = x + dx[k];
          let ny = y + dy[k];
          if (
            nx >= 0 &&
            nx <= 6 &&
            ny >= 0 &&
            ny <= 6 &&
            board[nx][ny] === 0
          ) {
            board[nx][ny] = 1; // 지나온길 다시 못돌아가게 1로 바꾸어줄 것!
            DFS(nx, ny);
            board[nx][ny] = 0; // 빽하는 지점
          }
        }
      }
    }

    board[0][0] = 1; // 꼭 체크 해주고 시작하기!
    DFS(0, 0);
    return answer;
  }
  let arr = [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 1, 1, 1, 1, 1, 0],
    [0, 0, 0, 1, 0, 0, 0],
    [1, 1, 0, 1, 0, 1, 1],
    [1, 1, 0, 0, 0, 0, 1],
    [1, 1, 0, 1, 1, 0, 0],
    [1, 0, 0, 0, 0, 0, 0],
  ];

  console.log(solution(arr)); //8
  // dx 행 dy 열 헷갈리지 말기!
  
  

⭐️ 기억할 점) DFS 함수를 실행하기 전 꼭 출발점을 1로 바꾸어주어 중복해서 다시 출발점으로 오지 못하게 할 것❗️ 지나온 점들도 다 1로 꼭 바꾸어주기❗️