[92일차]그래프 자료구조와 DFS, SNS예제를 통해 알아보자.

그래프와 탐색

자료구조를 학습하면서 트리를 탐색할 때에는 비교적으로,
계층적 구조를 가지기 때문에(부모가 있음) 재귀를 통해 탐색이 쉬웠다.
그러나, 그래프는 서로의 관계를 나타내는 간선만 있을 뿐더러, 계층구조 또한 존재하지 않는다.
그러나 의외로 방문한 곳을 표시 하는것만 빼면, 탐색하는 로직은 트리와 크게 다르지않다.

---

우선 예쁘고 실용적인 그래프를 만들어 보자.

예쁜그래프란?
나는 그래프의 제일 적절한 활용예를 sns친구목록이라 생각한다.
숫자놀이로 구현하는것은 예쁜그래프가 아니다!
부트캠프에서 좋은 뼈대를 내줬지만, 사람이름으로 관계도를 형성하는 그래프를 그리고 싶다.

내가 만들 그래프에는 constructor는 필요하지않다.

우선 constructor는 해당 class의 기본값을 설정한다.
하지만 기본값이 필요없다.
우선은 기초적인 CRUD기능을 만들어보자

C: create 그래프에 사람을 추가해보자

기본값은 없지만 이미 임의의 객체가 만들어질 준비가 된 상태다.
그래프 안에 사람을 추가해줄 메소드를 만들어보자.
동명이인일 경우는 일단 생각하지말자.

코드로 나타내보자!

class Graph{
  addPeople(name){
    this[name] = [];
  }
}

간단하지 않은가?
키값인 이름에 들어가는 밸류인 배열에 edge(관계)를 추가할거다
바로 만든 메소드를 활용해 사람을 추가해보자.

그림으로 나타낸다면?

people이라는 객체에 메소드를 통해 추가된 인원이 총 5명이다.
나중에 탐색 이해를 돕기 위해 두사람 더 추가하자.

R: read 서로의 관계를 확인하고, U: update 관계를 추가하자.

makeFriend라는 메소드를 통해 관계를 추가하자.
각 이름(키)에 해당하는 배열에 친구가 될 이름을 푸쉬한다.
그리고 둘이 친구면 true 친구가아니면 false를 내뱉자.

코드로 나타내보자!

class Graph{
  addPeople(name){
    this[name] = [];
  }
  
  makeFriend(name1, name2){
    this[name1].push(name2);
    this[name2].push(name1);
  }
 
  isFriend(name1, name2){
    if(this[name1].indexOf(name2) !== -1){
      return true;
    }
    return false;
  }
}

역시나 메소드를 통해 추가해보자.

그림으로 나타내면?

나만 인싸가 된 모습이다.
탐색을 용이하게 하기위해 관계를 더 복잡하게 형성하자.

isFriend메소드로 친구인지 확인하자

D: delete 아예탈퇴하는 메소드와, 친구관계를 끊는 메소드를 만들자.

아예 people이라는 객체를 나가버리는 leave메소드와,
서로의 친구관계만 끊어버리는 burnBridges를 만들어보자.

leave라는 메소드는 전체 친구목록에도 사라져야한다.

burnBridges 메소드는 서로의 관계만 끊어야 한다.

---

우선 내가 원하던 사람과 사람사이의 사이를 나타내는 그래프를 완성했다.
기본적인 CRUD기능을 만들었다면 이젠, Read를 극대화한 탐색기능을 구현해보자
그래프의 탐색에는 깊이우선탐색(DFS) 그리고 너비우선탐색(BFS) 가 있다

깊이를 우선으로 탐색한다는게 뭐에요?

다른곳 보면 말도참 어렵게도 했는데,
초등학생도 알아먹을만큼 쉽게 설명해본다.

1. 시작점 부터 방문기록을 남긴다. 방문을 안한곳 중 갈 수 있는데 까지 한길로 끝까지 일단 간다. 가는곳 마다 방문기록 남기는건 필수 ><

2. 더이상 갈 곳이 없으면 왔던길로 한번 돌아오자

3. 돌아왔는데 갈 곳이 있으면 또 그길로(방문안한곳만) 끝까지 간다.

재밌는 DFS 시작해보자!

우선 그림으로 먼저 그려보자.
아까 쓴 그림 그대로 쓸거다

1. 시작점 부터 방문을 안한곳 중 갈 수 있는데 까지 한길로 끝까지 일단 간다.

일단 박지상 부터 시작해서 욜씨미 가보자><
그림에서 방문기록은 체크로 표시한다

박지상에 방문함. 갈곳 네가지 있는데 첫번째 선택지인 박준석갈거임

박준석에 방문함. 박지상엔 방문했고 김제현 밖에 갈곳없음

김제현에 방문함. 박준석 방문했고, 갈곳 두가지있는데 박준석 방문했으니 그다음 순서인 이상권갈거임

이상권에 방문함. 왔는데 갈데없어서 돌아갈거임.

김제현으로 돌아옴. 왔는데 방문안한 곳이 김코딩뿐임.

김코딩에 방문함. 갈곳은 김해커뿐임

김해커에 방문함. 더이상 갈곳이 없음

김코딩으로 돌아옴. 갈곳없음

김제현으로 돌아옴. 갈곳없음

박준석으로 돌아옴. 갈곳없음

박지상으로 돌아옴. 갈곳 김용재 딱하나 있음

김용재로 돌아옴. 갈곳 아무데도 없음

함수종료

위와 같은 방식을 재귀로 쉽게 구현할 수 있다.
재귀함수의 베이스값이 바로 돌아오는 역할을 한다!

우선 각 노드마다 방문했는지 여부를 알 수 있는 장치를 만들자.

각각 회원들의 밸류값을 2차원배열로 바꾸고
0번째 인덱스에는 친구목록
1번째 인덱스에는 방문여부 를 넣어준다.

DFS까지 구현한 코드

class Graph{
  //SNS에서의 회원가입이라고 생각하자.
  addPeople(name){
    this[name] = [[],false];
  }
  
  //SNS에서의 친구추가라고 생각하자.
  makeFriend(name1, name2){
    this[name1][0].push(name2);
    this[name2][0].push(name1);
  }
  
  //두 인자가 친구인지 확인한다.
  isFriend(name1, name2){
    if(this[name1][0].indexOf(name2) !== -1){
      return true;
    }
    return false;
  }
  
  //SNS에서의 회원탈퇴라고 생각하자.
  leave(name){
    delete this[name];
    for(let key in this){
      if (this[key][0].indexOf(name) !== -1){
        this[key][0].splice(this[key][0].indexOf(name), 1);
      }
    }
  }
  
  //SNS에서 친구삭제라고 생각하자. 차단이라 생각해도 좋다.
  burnBridge(name1, name2){
    let idx1 = this[name1][0].indexOf(name2);
    let idx2 = this[name2][0].indexOf(name1);
    this[name1][0].splice(idx1, 1);
    this[name2][0].splice(idx2, 1);
  }
 
  //깊이우선탐색을 한다. start값에는 어느 노드가 들어가도 무방하다.
  DFS(start, callback){
    //먼저 방문기록을 남긴다.
    this[start][1] = true;
    // 현재 노드에 할려는 행위를 한다 
    callback(start);
    //방문을 안한곳 중 갈 수 있는데 까지 간다.
    //더이상 갈 곳이 없으면 왔던길로 한번 돌아오자(재귀했던 함수가끝남)
    //돌아왔는데 갈곳이 있다면 가자.
    for(let friend of this[start][0]){
      if(!this[friend][1])this.DFS(friend, callback);
    }
    //갈곳이 없으면 함수가 종료된다.
    //이 모든게 재귀로 가능!
  }
 
  //방문기록을 초기화한다.
  resetHistory(){
    for(let history in this){
      this[history][1] = false;
    }
  }
}

잘 작동하는지 확인해 보자.

const people = new Graph;
people.addPeople('박지상');
people.addPeople('이상권');
people.addPeople('김코딩');
people.addPeople('김해커');
people.addPeople('김용재');
people.addPeople('김제현');
people.addPeople('박준석');
people.makeFriend('박지상','박준석');
people.makeFriend('박지상','이상권');
people.makeFriend('박지상','김용재');
people.makeFriend('박지상','김해커');
people.makeFriend('박준석','김제현');
people.makeFriend('이상권','김제현');
people.makeFriend('김코딩','김제현');
people.makeFriend('김코딩','김해커');

우선은 아까 계속 예시를 들었던 그림과 같이 친구들을 추가해준다.

SNS의 이웃이나 친구를 넘나들면서
광고를 남겨대는 사람 들을 보았는가?
어쩌면 사람이 아닐수도 있다.

광고봇을 콜백함수로 만들어보자

const adBot = friend=>console.log(`${friend}의 방명록에 광고남김`)
people.DFS('박지상', adBot);

믿기힘들겠지만 광고봇이다. 그렇다고 해줘..
시작점을 정하고 메소드를 실행시키자.

아까 그림의 순서대로 광고를 남긴걸 볼 수 있다.

다른사람을 포인트로 해도 작동하는지 보자.

우선 광고봇이 헷갈리지않게 방문기록을 초기화시켜준다.

기록이 잘 초기화 되었다.
김코딩을 넣고 실행시켜보자.

훌륭하게 임무를 수행하는 광고봇이다.
다음엔 알고리즘 카테고리에서 너비우선탐색인 BFS 를 알아보자

---

위 코드는 모두 필자의 머릿속에서 작성됐습니다.
참조해서 올리실때 댓글만 달아주시면 압도적감사!