자바스크립트로 보는 완전 탐색

Doozuu·2026년 1월 7일

BFS DFS 브루트포스 비트마스크 완전 탐색 재귀

알고리즘&자료구조 (JS)

목록 보기

33/36

완전 탐색이란?

완전 탐색은 가능한 모든 경우의 수를 전부 탐색하여 정답을 찾는 기법이다.
이름 그대로 하나도 빠짐없이 모든 경우를 확인한다는 뜻이다.

다른 최적화 기법을 사용하지 않더라도 반드시 정답을 찾을 수 있다는 장점이 있지만,
경우의 수가 많아질수록 시간이 급격히 증가하는 단점이 있다.

완전 탐색은 어떤 경우에 쓰는가?

완전 탐색은 다음 조건을 만족할 때 사용한다.

모든 경우를 확인해야 하는 문제일 때
경우의 수가 감당 가능한 크기일 때

완전 탐색은 모든 경우를 전부 확인하므로 시간이 오래 걸릴 수 있다.
따라서 시간 복잡도 계산이 매우 중요하다.

일반적으로 약 10⁸번 이하의 연산은 시간 제한 내에 가능하다.
입력 크기와 경우의 수를 미리 계산하여 완전 탐색이 가능한지 판단한 뒤 사용해야 한다.

N ≤ 20 → 부분집합 (2ⁿ) 가능
N ≤ 8 → 순열 (N!) 가능
N ≤ 100,000 → 완전 탐색 불가능

완전 탐색은 어떻게 구현하는가?

완전 탐색은 구현 방식에 따라 여러 가지 알고리즘으로 나뉜다.

1. 브루트포스 (Brute Force)

가장 단순한 방식으로 반복문을 사용해 모든 경우의 수를 무식하게 탐색한다.

구현이 가장 쉽다.
경우의 수가 매우 적을 때 사용한다.

2. 재귀 (Recursion)

재귀 함수를 사용해 모든 선택을 단계적으로 탐색한다.
깊이(depth)를 기준으로 경우를 쌓아간다.

조합, 순열, 부분집합 문제에 자주 사용된다.

3. 비트마스크 (Bitmask)

각 상태를 이진수(bit) 로 표현하여 완전 탐색하는 방법이다.

상태가 선택 / 미선택처럼 두 가지로만 나뉠 때 적합하다.
부분집합 문제에서 자주 사용된다.

부분집합 구하기

const arr = ['A','B','C'];
const n = arr.length

// 1 << 3 = 1000 = 2^3 = 8
for(let mask=0;mask<(1 << n);mask++){
  const subset = [];

  for(let i=0;i<n;i++){
    // 각각의 마스크에 대해 자리별로 선택 여부 체크
    // 1 << 0 = 001, 1 << 1 = 010, 1 << 2 = 100
    if(mask & (1 << i)){
      subset.push(arr[i]);
    }
  }

  console.log(subset)
}

4. 백트래킹 (Backtracking)

완전 탐색 중에 더 이상 탐색할 필요가 없는 경우를 미리 차단(가지치기) 하는 기법이다.

완전 탐색 + 최적화
탐색 속도를 크게 줄일 수 있다.

예시)

현재 합이 이미 정답보다 커졌다면 중단
조건을 만족하지 않으면 더 내려가지 않음

대부분의 실전 문제에서 완전 탐색을 그대로 쓰기보다는 백트래킹과 함께 사용한다.

5. DFS / BFS

그래프 구조에서 모든 정점이나 모든 경로를 탐색하는 완전 탐색 방식이다.

DFS: 깊이 우선 탐색
BFS: 너비 우선 탐색

자주 사용되는 문제 유형:

미로 탐색
최단 거리
영역 탐색
경로 존재 여부 판단

특히 BFS는 최단 거리 문제에서 강력하다.

관련 문제 풀어보기

[백준] 도영이가 만든 맛있는 음식

난이도 : 실버 2
문제 링크 : https://www.acmicpc.net/problem/2961

분석

재료는 적어도 하나 이상 쓰기
신 맛은 곱, 쓴 맛은 합
신 맛과 쓴 맛이 차이가 가장 작은 경우를 반환

모든 재료에 있어 선택/미선택으로 나뉘므로 부분집합을 활용해 풀어준다.
각각의 부분집합에 대해 신 맛은 곱, 쓴 맛은 합하여 가장 작은 경우를 갱신해준다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const N = +input.shift();
const ingredients = input.map(i => i.split(' ').map(Number));
let answer = Infinity;

for(let mask=1;mask<(1<<N);mask++){
  const subset = [];

  for(let i=0;i<N;i++){
    if(mask & (1 << i)){
      subset.push(ingredients[i])
    }
  }

  let sour = 1;
  let bitter = 0;

  for(let j=0;j<subset.length;j++){
    const [s,b] = subset[j];
    sour *= s 
    bitter += b
  }

  answer = Math.min(answer, Math.abs(sour - bitter))
}

console.log(answer)

[백준] 감시

난이도 : 골드 3
문제 링크 : https://www.acmicpc.net/problem/15683

cctv 종류별로 회전 가능한 방향을 미리 설정해둔다. (위: 0, 오른쪽: 1, 아래: 2, 왼쪽:3)
1번 : 네 방향 (상하좌우)
2번 : 두 방향 (수평/수직)
3번 : 네 방향 (직각)
4번 : 네 방향
5번 : 한 방향
cctv 위치와 종류를 미리 찾아둔다. (모든 cctv를 회전시키며 탐색해야 하므로)
정해진 방향을 모두 감시 상태로 만드는 함수를 미리 정의한다.
- dx,dy 배열 미리 만들어두기 (위,오른쪽,아래,왼쪽 순서)
- 맵을 벗어나거나 벽(6)인 경우 감시 종료하기
- 그 외의 경우 모두 감시 상태(-1)로 만들기
DFS로 모든 경우의 수를 탐색한다.
- 첫 번째 cctv부터 감시 시작
- 타입에 맞는 cctv 회전 방향 찾기
- 각 회전 방향에 대해 감시 진행
- 그 다음 cctv 회전 진행(재귀)
- 모든 cctv 회전 완료하면 사각지대(0) 수 카운트해서 최솟값 갱신

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const board = input.slice(1).map(line => line.split(' ').map(Number));
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
const directions = [
  [],
  [[0], [1], [2], [3]],
  [[0, 2], [1, 3]],
  [[0, 1], [1, 2], [2, 3], [3, 0]],
  [[0, 1, 2], [1, 2, 3], [2, 3, 0], [3, 0, 1]],
  [[0, 1, 2, 3]]
];

const cctvs = [];
let answer = Infinity;

// CCTV 위치 저장
for (let i = 0; i < N; i++) {
  for (let j = 0; j < M; j++) {
    if (board[i][j] >= 1 && board[i][j] <= 5) {
      cctvs.push([i, j, board[i][j]]);
    }
  }
}

// 맵 복사
function copyMap(map) {
  return map.map(row => [...row]);
}

// 감시
function watch(x, y, dir, map) {
  let nx = x;
  let ny = y;

  while (true) {
    nx += dx[dir];
    ny += dy[dir];

    if (nx < 0 || nx >= N || ny < 0 || ny >= M) break;
    if (map[nx][ny] === 6) break;

    if (map[nx][ny] === 0) {
      map[nx][ny] = -1;
    }
  }
}

function dfs(idx, map) {
  if (idx === cctvs.length) {
    let count = 0;
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < M; j++) {
        if (map[i][j] === 0) count++;
      }
    }
    answer = Math.min(answer, count);
    return;
  }

  const [x, y, type] = cctvs[idx];

  for (const dirSet of directions[type]) {
    const copied = copyMap(map);

    for (const dir of dirSet) {
      watch(x, y, dir, copied);
    }

    dfs(idx + 1, copied);
  }
}

dfs(0, board);

console.log(answer);

[백준] 미친로봇

난이도 : 골드 4
문제 링크 : https://www.acmicpc.net/problem/1405

상하좌우로 N번만큼 움직일 때 같은 곳을 다시 방문하지 않을 확률을 구해야 한다.
방문 여부 체크를 위해 2*n+1 x 2*n+1 크기의 배열을 만들었다. (시작 지점을 (n,n)으로 하고 최대 +n, -n 만큼 움직이기 때문)
확률 단위는 %이기 때문에 미리 100으로 나누어 두었다.

이후 상하좌우로 이동하며 맵을 벗어나거나 이미 방문한 경우는 건너 뛴다.
확률은 계속 곱하고 방문 횟수도 depth로 카운트하며 N번 만큼 이동을 완료했을 때 확률을 더해준다.
백트래킹으로 방문 여부를 조절하며 효율화했다.

const fs = require('fs');
const input = fs.readFileSync(process.platform === 'linux' ? '/dev/stdin' : './test.txt').toString().trim().split('\n');
const [n, E, W, S, N] = input[0].split(' ').map(Number);
const visited = Array.from({length: n*2+1}, () => Array(n*2+1).fill(false));
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
const percent = [N,E,S,W].map(p => p / 100);
let answer = 0;
visited[n][n] = true;

function dfs(x, y, depth, p) {
  if(depth === n){
    answer += p;
    return;
  }

  for(let i=0;i<4;i++){
    const nx = x+dx[i];
    const ny = y+dy[i];

    if(nx < 0 || nx >= 2*n+1 || ny < 0 || ny >= 2*n+1) continue;
    if(visited[nx][ny]) continue;

    visited[nx][ny] = true;
    dfs(nx, ny, depth+1, p*percent[i]);
    visited[nx][ny] = false;
  }
}

dfs(n, n, 0, 1);

console.log(answer);