[비선형] 5. DFS

in 자료구조 on 비선형




  • 트리나 그래프 등에서 하나의 노드에 최대한 깊게 들어가면서 해를 찾는 탐색 기법
  • 장점 : 인접한 후보 노드만 기억하면 되므로 적은 기억공간 소요, 노드가 깊은 단계에 있을 경우 빠르게 정답 산출
  • 단점 : 선택한 경로가 답이 아닐 경우 불필요한 탐색 가능, 최단 경로를 구할 시 찾은 해가 정답이 아닐 경우 발생
  • 재귀를 이용한 탐색 : Graph._dfsRecursiveVisit()
  • 스택을 이용한 탐색 : Graph._dfsLoopVisit()



2. DFS 구현하기

그래프

재귀를 이용한 구현

function Graph() {
  this.edge = {};
  this.visited = {};
}

// addVertex() : 정점(vertex) 추가
Graph.prototype.addVertex = function (v) {
  this.edge[v] = [];
  this.visited[v] = false;
};

// addEdge() : 간선(edge) 추가
Graph.prototype.addEdge = function (v1, v2) {
  this.edge[v1].push(v2);
};

// print() : 현재 graph 연결 상태 출력
Graph.prototype.print = function (vertex) {
  for (let vertex in this.edge) {
    let neighbors = this.edge[vertex];
    if (neighbors.length == 0) continue;

    process.stdout.write(`${vertex} -> `);
    for (let i = 0; i < neighbors.length; i++) {
      process.stdout.write(`${neighbors[i]} `);
    }

    console.log("");
  }
};

// dfs() : DFS 탐색
Graph.prototype.dfs = function (startVertex) {
  this._dfsRecursiveVisit(startVertex);
};

// _dfsRecursiveVisit() : 재귀를 이용한 DFS 탐색
Graph.prototype._dfsRecursiveVisit = function (vertex) {
  // 1. 종료 조건
  if (this.visited[vertex]) {
    return;
  }

  // 2. 재귀 호출을 하면서 수행해야할 코드
  this.visited[vertex] = true;
  console.log(`visit "${vertex}"`);

  let neighbors = []
  neighbors = this.edge[vertex]

  for (let i = 0; i< neighbors.length; i++){
    this._dfsRecursiveVisit(neighbors[i])
  }
};

let graph = new Graph();
let vertices = ["A", "B", "C", "D", "E", "F", "G", "H", "I"];

for (let i = 0; i < vertices.length; i++) {
  graph.addVertex(vertices[i]);
}

graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("A", "D");
graph.addEdge("B", "E");
graph.addEdge("B", "F");
graph.addEdge("C", "G");
graph.addEdge("D", "G");
graph.addEdge("D", "H");
graph.addEdge("E", "I");

graph.print();
console.log("");

graph.dfs("A")
// visit "A"
// visit "B"
// visit "E"
// visit "I"
// visit "F"
// visit "C"
// visit "G"
// visit "D"
// visit "H"



스택을 이용한 구현

// dfs() : DFS 탐색
Graph.prototype.dfs = function (startVertex) {
  this._dfsLoopVisit(startVertex);
};

// _dfsLoopVisit() : 스택을 이용한 DFS 탐색
Graph.prototype._dfsLoopVisit = function (vertex) {
  let stack = new Stack()
  stack.push(vertex)

  while (!stack.isEmpty()){
    let vertex = stack.pop()
    if (this.visited[vertex]){
      continue
    }

    this.visited[vertex] = true;
    console.log(`visit "${vertex}"`);
  
    let neighbors = this.edge[vertex]
  
    for (let i = neighbors.length-1; i >= 0; i--){
      stack.push(neighbors[i])
    }
  }
};



3. 문제 - 바이러스

최근 웜 바이러스가 네트워크를 통해 전파되고 있는데, 한 컴퓨터라도 이 바이러스에 걸리면 컴퓨터와 연결되어 있는 모든 컴퓨터는 바이러스에 걸리게 된다.
현재 PC에 설정된 네트워크 기준으로, 한대의 PC에 바이러스가 걸렸을 때 총 몇 대의 PC가 바이러스에 걸릴지 계산하는 프로그램을 작성하시오.
예를 들어 7번까지의 PC가 있고, 1,2,3,5,6번 PC는 1번 네트워크, 4,7번 PC는 2번 네트워크로 구성되어 있을 때, 1번 pc가 바이러스에 걸리면 총 5대의 pc가 바이러스에 걸리게 된다.
입력은 pc의 총 대수와, pc와 pc가 연결된 네트워크 정보가 배열로 입력된다.
웜 바이러스에 감염된 pc는 무조건 1번으로 고정될 때, 바이러스에 걸리는 총 pc의 대수를 계산하여 반환하시오

function Graph() {
  this.edge = {};
  this.visited = {};
}

Graph.prototype.addVertex = function (v) {
  this.edge[v] = [];
  this.visited[v] = false;
};

Graph.prototype.addEdge = function (v1, v2) {
  this.edge[v1].push(v2);
  this.edge[v2].push(v1);
};

Graph.prototype.dfs = function (vertex) {
  if (this.visited[vertex]) return;

  this.visited[vertex] = true;
  let neighbors = this.edge[vertex];
  for (let i = 0; i < neighbors.length; i++) {
    this.dfs(neighbors[i]);
  }
};

function answer(v, e_list) {
  let result = 0;
  // 구현

  let g = new Graph();
  // 1. addVertex : PC 추가
  for (let i = 1; i <= v; i++) {
    g.addVertex(i);
  }

  // 2. addEdge : 네트워크 연결 (무방향)
  for (let i = 0; i < e_list.length; i++) {
    let e = e_list[i];
    g.addEdge(e[0], e[1]);
  }

  // 3. dfs 방문한 pc를 업데이트
  g.dfs(1);

  // 4. visited[vertex] > 방문 ? true : false
  for (let vertex in g.visited) {
    result += g.visited[vertex] ? 1 : 0;
  }
  // 구현 종료
  return result;
}

let input = [
  // TC : 1
  [
    7,
    [
      [1, 2],
      [2, 3],
      [1, 5],
      [1, 5],
      [5, 2],
      [5, 6],
      [4, 7],
    ],
  ],
  [
    10,
    [
      [8, 6],
      [5, 7],
      [9, 10],
      [7, 4],
      [1, 8],
      [5, 10],
      [7, 2],
    ],
  ],
  [
    10,
    [
      [6, 9],
      [9, 4],
      [4, 8],
      [9, 7],
      [6, 8],
      [10, 1],
      [10, 9],
    ],
  ],
];

for (let i = 0; i < input.length; i++) {
  process.stdout.write(`#${i + 1} `);
  console.log(answer(input[i][0], input[i][1]));
}

// #1 5
// #2 3
// #3 7



4. 문제 - 타겟넘버

programmers 

function dfs(numbers, target, index, total) {
  if (index === numbers.length) {
    return target === total ? 1 : 0;
  }

  let count = 0;
  count += dfs(numbers, target, index + 1, total + numbers[index]);
  count += dfs(numbers, target, index + 1, total - numbers[index]);

  return count;
}

function solution(numbers, target) {
  return dfs(numbers, target, 0, 0);
}