[JS|알고리즘] 자바스크립트(javascript)의 백트래킹(Backtracking) 알아보기

 

백트래킹?

Back + Tracking, 합성어인만큼 각 단어에 대해 감을 잡아보려고 한다.

 

Tracking : 따라가다. 추적하다

'tracking'이라는 단어를 보면 마블 시네마틱 유니버스의 <가디언즈 오브 갤럭시> 내 등장인물 욘두가 생각난다..!?

 

출처 : '욘두 우돈타(마블 시네마틱 유니버스)' 나무위키

 

 

괴물(목표)을 잡기 위해 가장 최적화된 경로를 따라 이동하는 화살의 이미지가 바로 Tracking인 것 같다.

Tracking

다시 말해서, 'Tracking'이란 목표를 향해 특정 경로를 따라서 가는 것이라고 볼 수 있으며,

이는 곧 탐색용 알고리즘의 특징과도 같다고 생각하였다.

이 전 포스트들에서도 알아봤었던, 그래프 탐색 알고리즘들과의 비교를 해보려고 한다.

 

[JS|알고리즘] 자바스크립트(javascript)의 DFS/BFS(그래프 탐색 순회) 알아보기

 

 

≈ 그래프 탐색 알고리즘

- DFS의 경우, 길을 탐색할 때 내가 있는 곳(시작지점)에서 가장 멀고 깊은 곳부터 확인을 한다.

DFS

 

- BFS의 경우, 길을 탐색할 때 내가 있는 곳(시작지점)에서 가장 가까운 곳(상하좌우)부터 확인을 한다.

BFS

 

 

- 다익스트라의 경우, 길을 탐색할 때 내가 있는 곳(시작지점)에서 가장 짧은 깊은 곳(최소경로)부터 확인을 한다.

다익스트라

 

 

그렇다면 Backtracking의 경우에는 어떠할까?

길을 탐색할 때 내가 있는 곳(시작지점)에서 가장 유망한 곳부터 확인하는 것이 Backtracking 알고리즘이다.

Backtracking

 

보다 더 쉽게 이해하기 위해 DFS와 비교해보자면,

DFS는 깊은 곳을 따라 이동하며 확인하다가, 가장 깊은 곳에 다다른다면 Back한다.

이와 다르게, Backtracking은 맞는 경로를 따라 이동하다가, 불필요한 경로탐색이라고 생각한다면 Back한다.

 

비교한 김에 'Backtracking이 오직 DFS만을 사용한다.'는 점에 대해 짚고 넘어가려고 한다.

 

Backtracking은 DFS를 활용한다?

이에 대해 확인하기 위해서는 Backtracking이 어디를 어떻게 탐색하고, 어디를 향해 돌아가느냐를 봐야한다.

 

Backtracking의 이동 경로

1. 자식 노드를 탐색하다가 (tracking)
2. 불필요한 탐색이라고 생각한다면(유망성 확인) => DFS와 다른 점!
3. 부모 노드로 돌아간다 (Back)

 

Backtracking은 DFS처럼 깊이 우선적으로 탐색을 진행할 수도 있다. (공통점)

하지만 DFS처럼 완전 탐색으로 진행하지 않고 유망한 곳(일부)만 탐색한다. (차이점)

 

따라서 DFS, Backtracking은 상-하(포함)의 관계가 아니라 공유의 관계라고 보는 게 알맞다.

Backtracking과 DFS는 공유의 관계

 

물론, BFS의 너비 우선 탐색을 사용하여 Backtracking을 구현할 수도 있다.

BFS, Backtracking

 

다만 Backtracking 알고리즘의 특성상,

DFS를 활용하는 경우가 훨씬 많기에 Backtracking과 DFS을 엮는 것이 흔히 보이는 것이다.

(왜 그러한지는 추후 Backtracking의 특징을 설명하며 알아가보자)

 

그렇다면, Backtracking의 특징은 무엇일까?

다익스트라 알고리즘의 경우, 방문하지 않은 곳 중 가장 작은 가중치를 가진 곳을 탐색한다는 특징이 있다.

 

Backtracking의 경우에는 어떠할까?

당연하게도 유망성(탐색을 진행해도 되나?에 대한 질문)을 판단하는 것이 가장 큰 특징이다.

 

그렇다면 유망성에 대해 두 가지 질문이 떠오를 수 있을 것 같다. 차근차근 알아가보자.

1. 유망성은 언제, 왜 판단하는가?
2. 유망성은 어떻게 판단하는가?

 

1. 유망성은 언제, 왜 판단하는가?

이는 곧, 왜 DFS와 엮는 일이 더 많을까에 대한 답변이 되기도 한다.

 

유망성은 불필요한 계산을 줄이고 싶을 때 사용한다.

Backtracking의 대표적인 문제인 'N-Queen 문제'를 보자면 행/대각선에 이미 퀸이 있을 경우에는 탐색을 하지 않는 조건을 사용한다.

 

[JS|백트래킹] 프로그래머스 12952번. N-Queen

 

 

불필요한 계산을 줄이고 싶은 경우에 쓰이기에

하나씩 돌아가며 상하좌우를 살펴보는 BFS보다 재귀적인 구조로 조합이나 미로를 확인하는 DFS에 더 유용한 것이다.

 

2. 유망성은 어떻게 판단하는가?

유망성은 유망함수를 통해 판단한다.

해결책이 될 가능성이 있는지 판단하는 유망함수는 문제의 조건에 따라 그 내용이 달라진다.

 

문제의 해결 가능성을 따질 수 있는 조건이 있을 때 이를 확인하고 작업하는 것이 유망함수이다.

 

'N-Queen 문제'를 이어서 보자면, 문제의 해결 가능성을 따질 수 있는 조건은 '행/대각선에 이미 퀸이 있으면 놓지마라'이다.

 

조건을 만족한다면? 유망하지 않기에 Back한다.

조건을 만족하지 않는다면? 유망한 경로이기에 그대로 tracking한다. 

 

3. Backtracking 알고리즘의 특징을 정리해보자면...

앞서 해결한 유망성에 대한 두 가지 질문을 토대로 Backtracking 알고리즘의 특징을 정리해보자.

 

자바스크립트의 객체에 해시 함수를 적용하면 해시 테이블이 되듯이,

탐색 알고리즘에 유망 함수를 적용하면 Backtracking 알고리즘이 된다.

 

재귀를 통해 DFS처럼 탐색을 진행하다가, 유망 함수를 통해 유망성이 판단된다면 다음과 같이 진행한다.

 

유망하지 않다 : Back == 가지치기 == 재귀 호출 X

유망하다 : tracking == 재귀 호출

 

---

문제 풀이로 알아보는 Backtracking

이선협/박경록 저자의 코딩 테스트 합격자 되기 자바스크립트편 - 백트래킹 몸풀기 문제 47번.

문제 설명 및 조건

• 문제 : 정수 N을 입력받아서 1부터 N까지 숫자 중에서 합이 10이 되는 조합을 배열로 반환하기
• 조건
  • Backtracking 사용할 것.
  • 반환할 숫자 조합은 오름차순으로 정렬되어야 할 것.
  • 같은 숫자는 한 번만 선택할 것
  • 1 ≤ N ≤ 10

문제 분석 및 풀이

• 숫자 조합의 합(sum)을 계산해나가며 for 문 돌기 (조건 2, 3)
  • for문을 i=0; i++을 하면서 오름차순으로 진행 : 조건 2
  • for문 안에서 숫자 한 번만 선택 : 조건 3
  • 유망함수 : sum이 10보다 작을 경우(조건)에만 재귀 호출 (조건 1)
    • 유망하지 않음 : 10보다 클 경우에는 back (재귀 호출 x)
    • 유망함 : 10보다 작을 경우에는 재귀 호출

    // 유망함수
    if (sum + i <= 10) {
      tracking(i + 1, sum + i, numArr.concat(i)) // 유망함 => 재귀호출
    }

 

전체 코드

function solution(N) {
  const result = []

  function tracking(start, sum, numArr) {
    if (sum === 10) {
      result.push(numArr)
      return
    }

    for (let i = start; i <= N; i++) {
      // 유망성 확인
      if (sum + i <= 10) {
        tracking(i + 1, sum + i, numArr.concat(i)) // 유망한 경우, 재귀호출
      }
    }
  }

  tracking(1, 0, [])
  return result
}

console.log(solution(5)) // [[1, 2, 3, 4], [1, 4, 5], [2, 3, 5]]
// console.log(solution(2)) // []
// console.log(solution(7)) 
// [[1, 2, 3, 4], [1, 2, 7], [1, 3, 6], [1, 4, 5], [2, 3, 5], [3, 7], [4, 6]]