94.BFS,DFS

완전탐색 종류 중 BFS, DFS에 대해서 알아보자.

DFS(깊이우선탐색)

아래쪽 level로 내려갔다가 더이상 아래 level이 없으면 가장 가까운 부모 노드로 거슬러 올라간 뒤 탐색하지 않은 다른 자식 노드를 탐색하는 방식이다.

탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. -> 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있으면 그 노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
2번의 과정을 수행할 수 없을 때까지 반복한다.

특징

BFS에 비해 메모리를 덜 잡아먹고, 특정 경로가 존재하는지를 판단할 때 유용하다.(ex)미로 게임)

실전문제(프로그래머스 '네트워크')

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.
• computer[i][i]는 항상 1입니다.

function solution (n, computers)  {
  let answer = 0;
  // 방문 여부 체크
  let visited = [];
  
  function dfs (i) {
    visited[i] = true;
    for(let j = 0; j < n; j++) {
      if(!visited[j] && computers[i][j]) {
        dfs(j);
      }
    }
  }
  for(let i = 0; i < n; i++) {
    // 특정 인덱스에 방문하지 않았다면 해당 인덱스를 넘겨주면서 dfs호출 
    if(!visited[i]) {
      dfs(i);
      answer++;
    }
  }
  return answer;
}


const computers = [[1,1,0],[1,1,0],[0,0,1]];
solution(3,computers);

반복문을 돌려서 방문유무를 확인한다. 방문하지 않았다면, dfs함수를 탄다.

BFS(너비우선탐색)

시작점을 방문하고 인접한 정점을 차례대로 방문하는 검색방법으로 트리의 각 depth에 있는 노드의 인접노드를 탐색하는 방식이다.

탐색 시작 노드를 방문 처리를 하고, 큐(QUEUE) 자료구조에 노드를 삽입한다. ->큐에서 최상단 노드를 꺼내고, 인접노드를 탐색 후, 방문처리하고, 큐에 넣는다. -> 선입선출 구조에 따라 먼저 들어온 노드를 꺼낸 후, 꺼낸 노드의 인접 노드를 살핀다. -> 방문처리하지않은 노드를 방문하고, 큐에 넣는다. -> 큐가 빌 때까지 계속 반복한다.

특징

찾고자 하는 target node가 시작점으로부터 가까이 있다고 예상될 경우 사용한다. (ex)지도 목적지 최단거리, 페이스북에서 친구 추천)

실전문제(프로그래머스 '네트워크')

function solution(n, computers) {
 let answer = 0;
 let visited = [];
 let queue = [];

 for(let i = 0; i < n; i++) {
  if(!visited[i]) {
    bfs(i);
    answer++;
  }
 }
   
 function bfs(i) {
   visited[i] = true;
   queue.push(i);
   
   while(queue.length) {
     //제거한 node 
     const currentNode = queue.shift();
     
     for(let j = 0; j < computers[currentNode].length; j++) {
       //i가 아니라  currrentNode를 사용해야 함, i를 사용하면 그냥 지나가는 숫자가 생김
       if(computers[currentNode][j] && !visited[j]) {
         visited[j] = true;
         queue.push(j);
       }
     }
   }
 }
 return answer;
}