[node.js] 백트랙킹, 알고보면 쉽다! feat. BOJ - 14888

Seungrok Yoon (Lethe)·2023년 6월 19일

[알고리즘] Lethe와 함께 코테를

목록 보기

6/25

백트랙킹 소개

백트랙킹은 기본적으로 DFS를 활용한 탐색 방법입니다. DFS는 수형도 그리기를 통해 이해하니 쉬웠습니다.

수형도 그리기를 통한 백트랙킹 개념 이해

수형도를 그리는 방법에는 두 가지가 있어요. 첫 번째는 각 단계에서 선택할 수 있는 모든 경우를 적고, 다음 단계로 넘어가는 너비우선탐색(BFS), 두 번째는 각 단계에서 선택할 수 있는 경우 하나를 선택하고, 그 선택을 기반으로 다음 단계로 넘어가는 깊이우선탐색(DFS)이 바로 그것이죠.

가령 수 1,2,3을 한 번씩 사용해서 차례로 나열할 수 있는 경우를 DFS 수형도로 그려보겠습니다.

아래 그림은 DFS 가 아닌 BFS 탐색 방법입니다.

1번째 조합

DFS가 하면 이 그림이 옳겠어요.먼저 첫 번째 올 수 있는 수 (1,2,3) 중에 첫 번째 선택인 1을 선택했습니다.

첫 번째 선택에서 1을 선택한 채로 두 번째 단계에서도 선택 가능한 수들 중 하나를 정한 후, 다음 단계로 이동!

세 번째 단계(base case, 3개의 숫자들 중, 3개의 수를 다 고르게 되는 단계)에서도 같은 동작을 반복합니다. 그리고, 3개의 숫자들 중, 3개의 수를 다 골랐으니(1,2,3 순서로), 한 단계 뒤로 이동(백트랙킹)!

2번째 조합

이제 우리는 2번째 단계로 다시 돌아왔어요. 2번째 단계에 방문할 수를 다시 선택할 차례인 것이죠.
아까는 두 번째 수로 2를 선택했으니, 이번에는 3을 선택해야 합니다. 그 다음은 세 번째 수를 선택하는 일이겠죠?

세 번째 단계에서는 남은 선택지가 2니까, 2를 선택해주고, 3 개의 수를 다 골랐으니(1,3,2), 한 단계 뒤로 이동(백트랙킹)!

3번째 조합

이제 우리는 다시 2번째 단계로 돌아왔어요(도르마무...?). 2번째 단계에서 방문할 수를 다시 선택할 차례입니다.

어라? 그런데 이번에는 상황이 조금 달라요. 왜냐하면 2번째 단계에서 선택할 수 있는 수인 2와 3을 다 선택해서 끝까지 탐색을 마쳤기 때문입니다.

이런 경우에는 2번째 단계에 대한 탐색을 끝마쳤기에, 한 단계 뒤로 이동(백트랙킹) 해야겠어요.

이제 우리는 첫 번째 자리에 올 수를 선택해야 합니다. 아까는 첫 번째 수로 1을 선택한 경우에 대해서 끝까지 탐색했으니, 이번엔 2를 선택할 차례죠.

이후의 동작들

이후의 모든 동작들도 이와같이 진행이 될 것입니다. 여기서 핵심은 각 단계별로 '선택'을 한다는 것, 그리고 선택 이후 '우리가 원하는 단계까지 탐색'을 진행하고, 탐색이 끝나면 선택을 해제하여 '선택하기 전 상황을 원상복구'한다는 것이에요.

백트랙킹 코드 구현

기본 구조부터 코드를 짜 보도록 하죠. 우리는 세 개의 수를 대상으로 조합을 백트랙킹 방식으로 탐색할 예정이니, 이 수들을 배열에 담아두고, dfs 탐색을 진행할 함수를 하나 만들어주죠.

그리고 임시로 선택한 숫자들이 저장될 배열인 pool과, 최총 결과를 기록할 result 문자열변수도 하나 추가해주죠.

함수에는 현재 내가 속해있는 단계, 그리고 탐색을 원하는 최대 단계를 인자로 받아줍니다.

const arr = [1,2,3]
const pool = []
let result = ''

function dfs(currentStep, goalStep){
  return 0
}

dfs(0,3)

그럼 본격적으로 dfs 함수 내부를 작성해줍시다. dfs의 핵심은 한계 조건에 도달했을 때의 로직과, 재귀를 진행해야 하는 로직을 분리하는 것입니다. 한계 조건에 도달한 경우를 우리는 base case라고 부르기로 했어요. base case에 도달하게 되면 재귀문을 종료하게 되고, 이는 탐색이 종료되는 것과 동일한 의미를 지닙니다.

그리고 한계 조건에 도달하지 않는 경우에는 "어떻게 다음 탐색을 진행할 것인지?"에 대한 로직을 작성하면 되겠죠.

그러면 우리 base case부터 작성해보도록 합니다. 아래처럼 작성해주면 되겠네요.
우리가 원하는 재귀문의 종료 시점은, 현재 탐색하고 있는 단계가 우리가 목적지로 설정한 단계랑 동일해졌을 때, 즉 goalStep만큼의 수를 선택했을 시점이기 때문에 if 문 안의 조건을 아래처럼 작성한 것이고, 그 결과를 기록해준 것이지요.

const arr = [1,2,3]
const pool = []
let result = ''

function dfs(currentStep, goalStep){
  if(currentStep === goalStep){
    //이미 세 번의 선택을 진행한 상황이기에, pool에 있는 내용을 result로 기록해줍니다.
    result += pool.join(' ')+ '\n'
  	return 
  }
}

dfs(0,3)

다음으로 중요한 것은 "다음 탐색에 대한 진행방법" 을 잘 작성하는 것입니다. 수형도를 그릴 때를 생각해보죠. 우리 수형도를 그릴 때, 어땠나요? 각 단계에서 선택가능한 경우들을 하나 선택하고, 그 다음 탐색을 진행했었죠?

그러면 for 문 안에서 dfs함수를 호출하면 딱 맞겠네요! 아래처럼요.

const arr = [1,2,3]
const pool = []
let result = ''

function dfs(currentStep, goalStep){
  if(currentStep === goalStep){
    //이미 세 번의 선택을 진행한 상황이기에, pool에 있는 내용을 result로 기록해줍니다.
    result += pool.join(' ')+ '\n'
  	return 
  }
  for(let i =0; i< arr.length; i++){
    dfs(currentStep+1, goalStep)
  }
}

dfs(0,3)

이걸로 된 걸까요? 아니죠, 위 로직에서는 우린 아직 '선택'과, 탐색이 끝난 이후 '선택 해제'를 하지 않았어요. 그러면 프로그래밍적으로 어떻게 해야할까요?

바로 pool에 넣었다가, 탐색이 끝나면 빼는 것입니다.

이 부분이 처음에는 조금 이해가 어려울 수 있어요. 그런데 pool을 수형도라고 생각하고, 종이에 pool의 변화를 관찰해보면 이해가 쉽게 갈 것입니다.

const arr = [1,2,3]
const pool = []
let result = ''

function dfs(currentStep, goalStep){
  if(currentStep === goalStep){
    //이미 세 번의 선택을 진행한 상황이기에, pool에 있는 내용을 result로 기록해줍니다.
    result += pool.join(' ')+ '\n'
  	return 
  }
  for(let i =0; i< arr.length; i++){
    //arr[i]를 선택!
    pool.push(arr[i])
    //arr[i]를 선택한 채로 다음 탐색 진행
    dfs(currentStep+1, goalStep)
    //arr[i]를 선택 해제!
    pool.pop()
  }
}

dfs(0,3)

자~ 이제 거의 다 왔습니다. 하지만 위 코드는 완벽하지 않습니다. 왜일까요?

바로 중복이 허용되고 있기 때문이에요. 중복이 허용되고 있는 이유는 방문 처리를 우리가 하지 않아서입니다.
그럼 각 요소의 방문도 pool에 행한 것처럼 비슷하게 하면 되겠네요. 선택->방문처리->탐색->방문해제->선택해제. 이렇게요!

그러면 arr를 본딴 방문처리만 하는 배열을 새로 하나 만들어서 방문을 기록해보죠.

const arr = [1, 2, 3]
const visited = new Array(arr.length).fill(0)
const pool = []
let result = ''

function dfs(currentStep, goalStep) {
  if (currentStep === goalStep) {
    //이미 세 번의 선택을 진행한 상황이기에, pool에 있는 내용을 result로 기록해줍니다.
    result += pool.join(' ') + '\n'
    return
  }
  for (let i = 0; i < arr.length; i++) {
    //이미 방문한 곳은 건너뛰기
    if (visited[i]) continue
    //arr[i]를 선택!
    pool.push(arr[i])
    //방문기록
    visited[i] = 1
    //arr[i]를 선택한 채로 다음 탐색 진행
    dfs(currentStep + 1, goalStep)
    //방문해제
    visited[i] = 0
    //arr[i]를 선택 해제!
    pool.pop()
  }
}

dfs(0, 3)
console.log(result)

추가된 로직 확인하셨나요, 재귀를 하기 전에, 선택하는 숫자가 이미 선택되어 pool에 있는지, 그렇지 않은지를 체크해보았습니다. 만약 이미 선택된 숫자라면 다시 선택할 수 없어야겠죠? 그래서 continue문을 사용했습니다.

결과를 확인해보죠. 음 ~ very nice! 성공이네요. 그러면 우리 이 백트랙킹 로직을 조금 응용해서 BOJ_14888 연산자 끼워넣기 문제도 한 번 같이 풀어보도록 하죠.

BOJ_14888 연산자 끼워넣기 풀이


const input = require('fs')
  .readFileSync(process.platform === 'linux' ? 'dev/stdin' : 'test/test.txt')
  .toString()
  .trim()
  .split('\n')

const MAX = Number.MAX_SAFE_INTEGER
const MIN = Number.MIN_SAFE_INTEGER
const N = +input[0]
const numArr = input[1].split(' ').map(Number)

let [add, sub, mul, div] = input[2].split(' ').map(Number)
let max = MIN
let min = MAX

const dfs = (currDepth, targetDepth, calcResult) => {
  if (currDepth === targetDepth) {
    max = Math.max(max, calcResult)
    min = Math.min(min, calcResult)
    return
  }

  if (add > 0) {
    add -= 1
    dfs(currDepth + 1, targetDepth, calcResult + numArr[currDepth])
    add += 1
  }
  if (sub > 0) {
    sub -= 1
    dfs(currDepth + 1, targetDepth, calcResult - numArr[currDepth])
    sub += 1
  }
  if (mul > 0) {
    mul -= 1
    dfs(currDepth + 1, targetDepth, calcResult * numArr[currDepth])
    mul += 1
  }
  if (div > 0) {
    div -= 1
    dfs(currDepth + 1, targetDepth, parseInt(calcResult / numArr[currDepth]))
    div += 1
  }
}

dfs(1, N, numArr[0])
console.log(max === 0 ? 0 : max)
console.log(min === 0 ? 0 : min)