TIL1 | 완전 탐색 DFS BFS

hyseoseo·2021년 6월 30일

알고리즘

Algorithm

목록 보기

1/2

기반 개념

탐색 search: 많은 양의 데이터 중 원하는 데이터를 찾는 과정
스택: 선입후출
큐: 선입선출
재귀 함수: 수학의 점화식을 소스코드로 옮긴 것. 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것. 보통 점화식에서 종료 조건 찾을 수 있다.
함수는 메인 메모리의 스택에 저장되고, 마지막에 호출된 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료됨. 그러므로 재귀 함수 수행 = 스택 자료 구조 이용.

그래프 표현 방식

인접 행렬

2차원 배열. 연결 안된 노드끼리는 비용이 무한. 모든 관계를 저장하므로 노드 개수 많으면 메모리 낭비됨. but 연결 여부 빨리 탐색 가능

인접 리스트

linked list. 연결된 정보만 저장. 특정 노드와 연결된 모든 인접 노드를 순회해야 하는 경우 유리함.

DFS

탐색 시작 노드를 스택에 삽입하고 방문 처리
스택 최상단 노드에 방문하지 않은 인접 노드 있으면 스택에 넣고 방문 처리 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
2를 반복한다.

시간복잡도 O(N)

BFS

탐색 시작 노드를 큐에 삽입하고 방문 처리
큐에서 노드를 꺼내 해당 노드 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
2를 반복

시간복잡도 O(N)
최적해 보장. 주로 최단 거리 문제

2차원 배열 탐색 문제다? 그래프로 바꿔보자!

음료수 얼려먹기 - dfs

const ice = (n, m, map) => {
  const board = map;
  console.log(board);
  const result = 0;

  const dfs = (x, y) => {
    if (x <= -1 || x >= n || y <= -1 || y >= m) {
      return false;
    }
    if (board[x][y] === 0) {
      board[x][y] === 1;
      dfs(x - 1, y);
      dfs(x + 1, y);
      dfs(x, y - 1);
      dfs(x, y + 1);
      return true;
    }
    return false;
  };

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (dfs(i, j) === true) {
        result++;
      }
    }
  }

  return result;
};

const map = [
  [0, 0, 1, 1, 0],
  [0, 0, 0, 1, 1],
  [1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0],
];
console.log(ice(4, 5, map));

미로찾기 - bfs

const solution = (n, m, board) => {
  const queue = [];
  //상하좌우
  const dx = [-1, 1, 0, 0];
  const dy = [0, 0, -1, 1];

  const vfs = (x, y) => {
    queue.push([x, y]);
    while (queue.length) {
      const now = queue.shift();
      x = now[0];
      y = now[1];
      for (let i = 0; i < 4; i++) {
        let newX = x + dx[i];
        let newY = y + dy[i];
        if (newX < 0 || newX >= n || newY < 0 || newY >= m) continue;
        if (board[newX][newY] === 0) continue;
        if (board[newX][newY] === 1) {
          board[newX][newY] = board[x][y] + 1;
          queue.push([newX, newY]);
        }
      }
    }
    return board[n - 1][m - 1];
  };

  return vfs(0, 0);
};

const map = [
  [1, 0, 1, 0, 1, 0],
  [1, 1, 1, 1, 1, 1],
  [0, 0, 0, 0, 0, 1],
  [1, 1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1, 1],
];
console.log(solution(5, 6, map));

hyseoseo