29일차, Graph, Tree

2021.08. 27 금요일

1. Today's Key points!🔑

• Graph
• Tree
• bfs, dfs

2. 정리해보자!🧹

Graph(그래프)란? 컴퓨터 공학에서 이야기 하는 자료구조 그래프는 마치 거미줄처럼 여러개의 점들이 선으로 이어져 있는 복잡한 네트워크 망과 같은 모습을 가지고 있다. 즉, 그래프는 여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다. 간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다. 하나의 점을 그래프에서는 정점(vertex)이라고 표현하고, 하나의 선은 간선(edge) 이라고 한다.

그래프 실사용 예 : 포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 네비게이션 (길찾기) 등에서 사용하는 자료구조가 바로 그래프이다.

알아둬야 할 그래프 용어들

• 비가중치 그래프 : 간선이 두 정점을 이어주고있다는 사실만 알려줄 뿐, 그 외의 정보는 포함하고 있지 않는 그래프.
• 가중치 그래프 : 간선에 더 자세한 정보를 포함하고 있는 그래프.
• 무(방)향 그래프(undirected graph) : 정점간 이동이 양쪽으로 다 가능한 그래프.
• 단방향 그래프 : 한쪽으로만 이동이 가능한 그래프.
• 진입차수(in-degree) / 진출차수(out-degree) : 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇개인지를 나타낸다.
• 인접(adjacency) : 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점이다.
• 자기 루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다라고 한다. 다른 정점을 거치지 않는다는 것이 특징.
• 사이클(cycle) : 한 정점에서 출발해서 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현한다.

 

인접 행렬이란? 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬으로 2차원 배열의 형태로 나타낸다.                                  

from               \                     to	A	B	C
A	0	0	1
B	1	0	1
C	1	0	0

• A의 진출차수는 1개 : matrix[A][B] === 1 
• B의 진출차수는 2개 : matirx[B][A] === 1, matirx[B][C] === 1
• C의 진출차수는 1개 : matrix[C][A] === 1

인접 행렬은 언제 사용할까? 한 개의 큰 표와 같은 모습을 한 인접 행렬은 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이하다. 예를들어, A에서 B로 진출하는 간선이 있는지 파악하기 위해선 0 번째의 줄의 1 번째 열에 어떤 값이 저장되어있는지 바로 확인할 수 있다. 그리고 가장 빠른 경로를 찾고자 할 때 주로 사용된다.

인접 리스트란? 인접 리스트는 각 정점이 어떤 정점과 인접한지를 리스트의 형태로 표현한다. 각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트는 자신과 인접한 다른 정점을 담고 있다. 위의 matrix를 인접 리스트로 표현하면 다음 그림과 같다.

위 그림을 보면 B는 A와 C로 이어지는 간선이 두개가 있는데, A가 C보다 먼저있는 것을 볼 수 있다. 그런데 이 순서는 보통의 경우에는 그렇게 중요하지 않다. 그래프, 트리, 스택, 큐 등 모든 자료 구조는 구현하는 사람의 편의와 목적에 따라 기능을 추가/삭제할 수 있다. 그래프를 인접 리스트로 구현할 때, 정점별로 살펴봐야 할 우선 순위를 고려해서 구현할 수 있다. 이때, 리스트에 담겨진 정점들을 우선 순위별로 정렬할 수 있다. 우선 순위가 없다면 그냥 단순하게 나열한 리스트가 된다.

인접 리스트는 언제 사용할까? 메모리를 효율적으로 사용하고 싶을 떄 인접 리스트를 사용한다. 인접 행렬은 연결 가능한 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지하게 된다.

 

Tree란? 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태의 자료구조이다. 트리 구조는 데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결된 계층적 자료구조이다. 

위 그림처럼 트리 구조는 루트(Root) 라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다. 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하계층으로 연결되면 부모/자식 관계를 가진다. 위 그림에서 A는 B와 C의 부모 노드(Parent Node)이고, B와 C는 A의 자식 노드(Child Node)이다. 자식이 없는 노드는 리프 노드(Leaf Node)이다.

트리의 실사용 예 : 컴퓨터 디렉토리 구조, 토너먼트 대진표, 가계도(족보), 조직도 등.

Binary Search Tree(이진 탐색 트리)란? 우선, 이진트리(Binary tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리이다. 이 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있다. 이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이있다.

BFS(Breadth-First-Search) : 너비를 우선적으로 탐색하는 방법. 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적. 주로 두 정점 사이의 최단 경로를 찾을 때 사용. 코드상에서 Queue와 단짝.

DFS(Depth-First-Search) : 깊이를 우선적으로 탐색하는 방법. 모든 정점들을 한 번씩 방문(탐색)하는 것이 목적. 하나의 경로를 끝까지 탐색한 후, 찾는 것이 아니리면 다음 경로로 넘어가 탐색. 하나의 노선을 끝까지 들어가서 확인하고 다음으로 넘어가기 때문에, 운이 좋다면 단 몇 번만에 경로를 찾을 수 있다.

DFS와 BFS는 모든 정점을 한 번만 방문한다는 공통점을 가지고 있지만, 탐색순서가 다르기 때문에 해당 상황에 맞는 탐색기법을 사용해야 한다.

3. 코플릿 복기!🧐

👉🏻인접 행렬 생성하기

function createMatrix(edges) {
//방향이 있는 간선과 방향이 없는 간선들의 목록을 받는다.
//([
//     [0, 3, "directed"],
//     [0, 2, "undirected"], 
//     [1, 3, "directed"],   
//     [2, 1, "directed"],     
//])
//간선 목록에있는 것을 바탕으로 matrix의 사이즈를 구한다.
    let matrixSize = 0; 
  for(let i = 0; i < edges.length; i++){
    let max = Math.max(...edges[i].slice(0,2))
    if(matrixSize < max){
      matrixSize = max;
    }
  }
//구한 사이즈 만큼의 매트릭스를 만든다. +1을 해주는 이유는 위에서 구한 matrixSize는 사실 인덱스 값이기 때문에 길이가 되려면 +1을 해주어야한다. 
  let matrix = new Array(matrixSize+1).fill(0).map((el) => { 
    return el = new Array(matrixSize+1).fill(0);
  })
//매트릭스를 만들었으니 간선을 연결해준다.
  for(let i = 0; i < edges.length; i++){
    let [row, col, direct] = edges[i];
    if(direct === 'directed'){ //단방향일 경우
      matrix[row][col] = 1;
    }
    if(direct === 'undirected'){ //
      matrix[row][col] = 1;
      matrix[col][row] = 1;
    }
  }
  return matrix;
}

 

👉🏻인접 행렬 길찾기

function getDirections(matrix, from, to) {
//(
//     [    to
//      [0, 1, 0, 0],   
//from    [0, 0, 1, 0], 
//        [0, 0, 0, 1],
//        [0, 1, 0, 0],
//    ],
//    0,
//    2
//)
//인접행렬 정보를 받고, 정점 from에서 to로 가는 간선이 존재하는지를 확인해야 한다.
//아래의 방법이 BFS 탐색이다.
//우선 입력받은 from부터 탐색을 시작 queue에 from을 담아준다.
  let queue = [from]; 
  let isVisited = new Array(matrix.length).fill(false); // 정점을 방문(탐색)했다는 정보를 담기위한 배열을 만들어 준다. 
  isVisited[from] = true; // 현재 정점부터 시작하니까 그에 해당하는 정점을 true로 바꿔준다.
  while(queue.length > 0){ // 전부 탐색하다가 isVisited가 true로 가득차게 되면, queue는 빈 배열이 된다. 그래서 조건에 queue가 빈 배열이 될때까지
    let now = queue.shift(); // 현재 위치를 now라고 표현해주고 queue에서 정점을 빼온다.
    isVisited[now] = true; // 그리고 현재위치를 탐색했다는 표시를 해준다.
    if(now === to) return true; // 현재 있는곳이 to에 도달했다면 from에서 to로 가는 간선이 존재한다는 의미가 된다.
    for(let i = 0; i < matrix[now].length; i++){ // 현재 정점에서 다른 정점으로 가는 길이 있는지를 탐색
      if(matrix[now][i] === 1 && !isVisited[i]){ // 길이 있고, 탐색하지 않았던 곳이라면
        queue.push(i); //큐에 해당하는 정점을 넣어주고
        isVisited[i] = true; //방문했다는 표시를 해준다.
      }
    }
  }
  return false; //위의 과정을 모두 반복을 했는데도 찾지 못한다면 false를 
}

 

👉🏻연결된 정점들

이 문제는 앞서 푼 문제들이 복합된 문제이다.

연결된 정점의 컴포넌트(그룹들)가 몇 개인지를 찾아야 한다.

 이런식으로 연결이 되어있다면 리턴되어야 하는 값이 2이다.

이렇게 연결되어있는 vertex의 그룹이 몇개인지를 찾아야 한다.

 

 

 

 

👉🏻BFS탐색으로 문제 해결 ver.

function connectedVertices(edges) {
//간선 정보를 받기때문에 matrix를 만들어주려면 간선의 정보를 받아서 matrix 사이즈를 찾아야 한다.
//앞에서 매트릭스 만드는 것 해봤으니 설명 생략.
  let matrixSize = 0;
  for(let i = 0; i < edges.length; i++){
    let max = Math.max(...edges[i]);
    if(matrixSize < max){
      matrixSize = max;
    }
  }
  let matrix = new Array(matrixSize+1).fill(0).map((el) => {
    return el = new Array(matrixSize+1).fill(0);
  })
  // 매트릭스를 만들었으니 간선을 연결해준다. 간선은 무방향이니까 양쪽 다 연결.
  for(let i = 0; i < edges.length; i++){
    let [left, right] = edges[i];
    matrix[left][right] = 1;
    matrix[right][left] = 1;
  }
  //앞 문제들과 같이 방문을 표시하기 위한 배열을 만들고
  let isVisited = new Array(matrix.length).fill(false);
  let count = 0; // count는 이 문제에서 연결된 vertex그룹이 몇개인지를 세어야 한다.
 
  for(let i = 0; i < matrix.length; i++){ //이제 탐색을 할건데 
    if(!isVisited[i]){ // 방문하지 않았던 곳을 탐색할것임.
      bfs(matrix, i, isVisited); //아래에 따로 탐색하는 함수를 만들어 준다.
      //함수를 통해서 한 정점에서 연결되어있는 곳을 모두 탐색하고 연결이 끊겨있다면 함수를 빠져나와 count를 세어준다.
      //이 과정을 반복하면 vertex 그룹이 몇개인지를 알아낼 수 있게된다.
      count++;
    }
  }
  return count;
}
//앞서 했던 BFS 탐색 방법을 함수로 만든 것이다.
let bfs = function (matrix, vertex, isVisited){ //탐색하기 위해 입력받아야하는 정보는 matrix, vertex, isVisited가 된다.
  let queue = [vertex]; 
  isVisited[vertex] = true;
  while(queue.length > 0 ){
    let now = queue.shift();
    isVisited[now] = true;
    for(let i = 0; i < matrix[now].length; i++){
      if(matrix[now][i] === 1 && !isVisited[i]){
        queue.push(i);
        isVisited[i] = true;
      }
    }
  }
}
 

 

👉🏻DFS탐색으로 문제 해결 ver.

//bfs와 방법은 동일한데 함수만 바뀐것이다.
//edges = [[0,1],[2,3],[3,4],[3,5]]라고 해보자면
function connectedVertices(edges) {
  let matrixSize = 0;
  for(let i = 0; i < edges.length; i++){
    let max = Math.max(...edges[i]);
    if(matrixSize < max){
      matrixSize = max;
    }
  }
  let matrix = new Array(matrixSize+1).fill(0).map((el) => {
    return el = new Array(matrixSize+1).fill(0);
  })
 
  for(let i = 0; i < edges.length; i++){
    let [left, right] = edges[i];
    matrix[left][right] = 1;
    matrix[right][left] = 1;
  }
 
  let isVisited = new Array(matrix.length).fill(false);
  let count = 0; 
 
    //0 vertex에서 갈수있는 경로를 찾는데 dfs 함수를 통해서 1까지 찾고 연결된 곳이 없으므로 isVisited = [true, true, false, false, false, false]인 상태가 되고, count = 1이된다.
    //그다음 1에서 경로를 찾으려고 하는데 1은 탐색을 했던 곳이기 때문에 2로 넘어간다.
    //2 vertex에서 갈수 있는 경로를 찾는데 dfs 함수를 통해서 3이 연결되어있고 3은 4와 5가 연결되어있고 다음 경로가 없기 때문에 함수를 빠져나온다. 그럼 이때 isVisited = [true, true, true, true, true, true]가 되면서 모든 경로를 다 탐색했고 count = 2가 되면서 탐색을 종료한다.
    for(let i = 0; i < matrix.length; i++){ 
    if(!isVisited[i]){ 
      dfs(matrix, i, isVisited); 
      count++;
    }
  }
  return count;
}
//dfs는 재귀함수와 단짝이다. 왜냐하면 dfs는 한 정점에서 갈 수 있는 데 까지 쭉 가야하기 때문.
let dfs = function (matrix, vertex, isVisited){
  //dfs도 마찬가지로 탐색했던 곳은 탐색하지 않아야함.
  isVisited[vertex] = true;
 
 
    for(let i = 0; i < matrix.length; i++){ 
      if(matrix[vertex][i] === 1 && !isVisited[i]){ //간선이 존재하고 탐색하지 않았던 곳이라면
        dfs(matrix, i, isVisited); //재귀함수를 통해 해당경로에 들어간다. 이과정을 통해서 처음 시작한 정점부터 경로가 끊길때 까지 탐색을 하게된다.
      }
    }
}
 

이를 통해서 인접행렬을 생성하고 길을 찾고 하는 방법은 조금 익숙해 졌는데, 이걸 가지고 내가 다른 문제를 만났을 때 적용해서 풀 수 있을까 하는 의문이 들긴한다. 그래도 이렇게 하나씩 익숙해지다보면 '음.. 이건 이렇게 하면 되지않을까?' 하면서 문제를 풀고 있기를 기대해 본다.