Computer Science/Computer Algorithm

DFS

HJChung 2020. 9. 23. 19:36

1. 그래프 순회(탐색)

그래프란, 정점과 간선으로 이루어진 자료구조이다. 

출처: 예전에 공부했던 알고리즘 잡스

libertegrace.tistory.com/entry/3-ES6-Practice

 

5. Data Structure - Graph, Tree, BST

Graph 1)개념 : 노드(정점,Node, vertex) 와 간선(edge)로 구성된 자료구조 용어들 차수(Degree): 정점에 몇 개의 간선이 연결되어 있는가 사이클(Cycle): 자기 자신으로 다시 돌아올 수 있는 경로 2) 구현 그��

libertegrace.tistory.com

여기서 Graph와 Tree에 대해 정리한 적이 있는데, 둘 다 정점과 간선으로 이루어져있다. 

컴공에서 자료구조는 효율적인 접근 및 수정을 가능케하는 자료의 조직, 관리, 저장을 의미한다. 그러니까, 그래프 라는 자료구조에서도 데이터에 대해 매우 효율적인 접근 및 수정을 할 수 있어야 하겠다. 

 

그 방법은 무엇일까? 어떻게 정점(node)들을 돌아다니며 그 안에 무슨 값이 있는지를 효율적으로 탐색할 수 있을까?

방법1. 깊이 우선 탐색(DFS): 스택을 이용하는 방식이다. 

방법2. 너비 우선 탐색(BFS): 를 이용하는 방식이다. 

 

여기선 DFS에 대해 알아보고, DFS를 활용하여 풀 수 있는 알고리즘 문제를 모아서 리뷰해볼 것이다. 

2. DFS

1) DFS는

(발자취, 선행관계)와 밀접한 '스택' 자료구조를 이용하여 최대한 깊숙히, 많이 탐색해보는 그래프 탐색 방식이다. 

(즉, DFS를 이용할 때의 마음의 소리는 "갈 수 있는 만큼 가보고, 발자취를 남긴다. 막다른 길(더 갈 수 없는 상황)이 오면 내가 남긴 발자취를 보고 빠져나오지 뭐!" 이다. )

 

2) 방식

를 먼저 방문하고, 그 다음으로(이렇게 선행관계가 있다.) 나와 인접한 노드를 차례로 방문한다. 단, 방문했던 노드는 다시 가지 않는다. 

 

3) 예시

1. 

2. 

4) DFS 알고리즘 설계 (수도코드)

function DFS(currNode, visited){
    1. currNode(나)를 방문 , visited에 currNode저장 (한 번 간 곳은 또 가면 안되니까)
    2. currNode(나)와 인접한 모든 node(i)에 대해서 아래의 내용을 반복 (그러니까 반복문을 써야겠지)
    	3-1.만약  node(i) 가 아직 방문하지 않았다면
        	4. DFS(node(i), visited)
      	3-2. 방문했었다면 아무일도 해주지 않고 continue
   4. 결과 반환
 }

이렇게 재귀함수를 사용한다. 재귀 -> stack -> DFS.. 이렇게 발전(?) 해 나가는 고런 느낌..

 

5) DFS를 활용하여 풀 수 있는 알고리즘 문제

(문제 본문은 <더보기>를 클릭!)

 

1) treeDFSelect

더보기

/*

*

* 주어진 Tree 클래스에 `DFSelect` 메소드를 구현하세요.

*

* DFSelect 매소드의 요구사항은 아래와 같습니다.

* 1. filter 함수를 매개변수로 받습니다.

* 2. tree 의 각 node는 해당 filter 함수를 깊이 우선 방식으로 호출합니다.

* 3. filter 함수를 만족(return true)하는 tree의 node를 1차원 배열로 반환합니다.

*

*

* 예시 :

* let root1 = new Tree(1);

* let branch2 = root1.addChild(2);

* let branch3 = root1.addChild(3);

* let leaf4 = branch2.addChild(4);

* let leaf5 = branch2.addChild(5);

* let leaf6 = branch3.addChild(6);

* let leaf7 = branch3.addChild(7);

* root1.DFSelect(function (value, depth) {

* return value % 2;

* })

* // [1, 5, 3, 7]

*

* root1.DFSelect(function (value, depth) {

* return depth === 1;

* })

* // [2, 3]

*

*/

 

/*

* value를 저장하는 기본적인 tree입니다.

*/

let Tree = function (value) {
  this.value = value
  this.children = []
}

Tree.prototype.DFSelect = function (filter) {
  // TODO: Your code here!
  let resultArray = []
  let depth = 0

  function filterDFS(currNode) {
    //DFS1. 나 먼저 해야할 것 하고
    if (filter(currNode.value, depth)) { //depth를 함께 넣어준 것은 testcase의 예시에서 depth도 함께 count해주길 원했기 때문이다. 
      resultArray.push(currNode.value)
    }
    //DFS2. 나와 인접한 것들에 대해서 해야할 것 한다.
    depth++ // 3. 나와 인접한 것들 ( = tree에선 children들 이니까 depth 내려가고)
    for (let i = 0; i < currNode.children.length; i++) {
      filterDFS(currNode.children[i])
    }
    depth-- //4. 나와 인접한 것들 다 탐색한 후엔 원래 내 자리로 돌아와야하므로 depth 원상복귀
  }

  filterDFS(this)

  return resultArray
}

2) robotPaths 문제

더보기

/**

*

* A robot located at the top left corner of a 5x5 grid is trying to reach the

* bottom right corner. The robot can move either up, down, left, or right,

* but cannot visit the same spot twice. How many possible unique paths are

* there to the bottom right corner?

*

* make your solution work for a grid of any size.

*

*/

 

// A Board class will be useful

var makeBoard = function (n) {
  var board = []
  for (var i = 0; i < n; i++) {
    board.push([])
    for (var j = 0; j < n; j++) {
      board[i].push(false)
    }
  }
  board.togglePiece = function (i, j) {
    this[i][j] = !this[i][j]
  }
  board.hasBeenVisited = function (i, j) {
    return !!this[i][j]
  }
  return board
}
//          북, 남, 서, 동
let iDir = [-1, 1, 0, 0]
let jDir = [0, 0, -1, 1]
var goPath = function (board, n, iCurr, jCurr) {
  if (iCurr === n - 1 && jCurr === n - 1) {
    cnt++
    return
  } else {
    board.togglePieces(iCurr, jCurr) //DFS1. 나먼저 가보기
    for (let d = 0; d < 4; d++) {
      //DFS2. 나와 인접한 곳 중에서
      //동서남북으로 map을 벗어나지 않는 선에서 다 가본다 .
      let iNext = iCurr + iDir[d]
      let jNext = jCurr + jDir[d]
      if (iNext === -1 || iNext === n || jNext === -1 || jNext === n) {
        //테두리면 거기로 안가고
        continue
      } else {
        //테두리가 아니면
        //DFS3. 안가본 곳이 맞는가 확인
        if (board.hasBeenVisited(iNext, jNext) === false) {
          //안가본 곳이 맞으면
          goPath(board, n, iNext, jNext) // 거기서부터 다시 DFS시작
        }
      }
    }
    board.togglePiece(iCurr, jCurr) //나와서는 초기화
  }
}

let cnt
var robotPaths = function (n) {
  cnt = 0 //경로 개수
  let board = new makeBoard(n) //robot이 움직일 map을 만들고
  goPath(board, n, 0, 0)
  return cnt
}

3) treeCountLeaves

더보기

/**

* Implement the `countLeaves` function in this Tree class.

*

* A leaf node is any node in the tree that has no children. `countLeaves` should

* traverse the tree, and return the number of leaf nodes the tree contains.

*

* Illustration of a tree with three leaves:

*

* * <- root

* / \

* * * <- leaf

* / \

* * * <- leaf

* /

* * <- leaf

*

* Example usage:

* var root = new Tree();

* root.countLeaves(); // 1

* root.addChild(new Tree());

* root.countLeaves(); // still 1

* root.addChild(new Tree());

* root.children[0].addChild(new Tree());

* root.children[0].addChild(new Tree());

* root.children[0].children[0].addChild(new Tree());

* root.countLeaves(); // 3

*

*/

 

/*

* Basic tree that stores a value.

*/

var Tree = function (value) {
  this.value = value
  this.children = []
}
//1. root부터 시작해서
//2. tree 탐색한다.
//3. 자신의 this.children의 length가 0이면 leatCnt++
//4. 0이 아니면 그 children으로 내려가서 계속 탐색하는 식의 DFS.
//5. leafCnt 초기화 문제를 없애려면 처음 countLeaves할떼 leafCnt가 0이 되길 원한다면,
//    countLeaves시작시 leafCnt를 선언하고 0으로 초기화해주면 되고
//    2~3은 countLeaves 안에 함수를 선언해서 내부 scope에서 leafCnt가 증가되도록 한다.
Tree.prototype.countLeaves = function () {
  let leafCnt = 0
  function CountCurrLeaf(currNode) {
    if (currNode.children.length === 0) {//DFS1. 나 먼저 해야할 것 하고
      leafCnt++
    } else {//DFS2. 나와 인접한 것들에 대해서 해야할 것 한다.
      for (let i = 0; i < currNode.children.length; i++) {
        CountCurrLeaf(currNode.children[i])
      } //이 문제는 leaf의 누적 문제이기때문에 재귀를 빠져나오더라도 초기화는 안해줘도 된다. 
    }
  }

지금까지 DFS 알고리즘에 대해 정리해 보았다.

아래는 알고리즘 공부필기본이다.

 

꼭 백지코딩으로 복습해보자! (이것 모두 나 자신에게 하는 말 입니더..)

 

'Computer Science > Computer Algorithm' 카테고리의 다른 글

정수론 - 소수  (0) 2020.10.22
정수론 - 최대공약수, 최소공배수 (유클리드 호제법)  (0) 2020.10.22
삽입정렬  (0) 2020.09.03
버블정렬  (0) 2020.05.20
선택정렬  (0) 2020.05.20