[코딩테스트] Java - 백트래킹

백트래킹

- 완전탐색: dfs, bfs처럼 데이터를 전부 확인하는 방법

- 백트래킹(backtracking): 가능성이 없는 곳에서는 되돌아가고, 가능성이 있는 곳을 탐색하는 알고리즘

- 유망함수(promising function): 특정 조건을 정하는 함수

 

(백트래킹 풀이법)

1. 유효한 해의 집합을 정의

2. 정의한 집합을 그래프로 표현

3. 유망함수 정의

4. 백트래킹을 통한 해 탐색

 

(부분 집합 합)

- 부분 집합 합(sum of subset): 1부터 N까지 숫자르 조합했을 때 합이 K가 되는 조합을 찾는 문제

- 유망함수1: 현재 조합으로 합이 K일 경우 탐색 중지

- 유망함수2: 해당 숫자를 조합하여 합이 K 이상이 되면 탐색 중지

 

(N-Queen)

- N-Queen: 체스의 퀸을 N x N 체스판에 N개 배치시 서로 공격할 수 없는 위치에 놓을 수 있는 방법의 수를 찾는 문제. 퀸은 상하좌우대각으로 이동 가능

- 유망함수: 퀸 추가시 동일 행이나 열, 대각선 방향에 중복된 퀸 존재시 탐색 중지

 

예제

(1부터 N까지 숫자 중 합이 K가 되는 조합)

- 유망함수1: 조합한 숫자의 합이 K일 경우 리스트에 추가

- 유망함수2: 조합한 숫자의 합이 10보다 크면 백트래킹

 

- 입력: N, K

- 출력: 합이 K가 되는 숫자들의 리스트(2차원 배열)

 

 

(스도쿠 퍼즐)

- 스도쿠 퍼즐: 9 x 9 스도쿠 보드를 다 채원 완성된 스도쿠 보드를 반환

- 스도쿠 퍼즐 조건1: 가로줄, 세로줄에는 1부터 9까지의 숫자가 한 번씩 나타나야 함

- 스도쿠 퍼즐 조건2: 9 x 9 보드를 채울 9개의 작은 박스(3 x 3 크기)에도 1부터 9까지의 숫자가 한 번씩 나타나야 함

- 유망함수1: 해당 행에 넣으려는 숫자가 있는지 확인

- 유망함수2: 해당 열에 넣으려는 숫자가 있는지 확인

- 유망함수3:  해당 위치를 포함하는 3 x 3 박스에 넣으려는 숫자가 있는지 확인

 

- 입력: board(2차원 행렬의 스도쿠 퍼즐)

- 출력: 2차원 행렬