백트래킹

N-Queen 어디감?

백트래킹은 사실 엄청 어렵다고 생각한다. 이론적으로는 쉬운데, 그걸 실제 문제에 적용하기가 진짜 어렵다고 느낀다.

그래도 문제는 풀어야겠으니 유형을 좀 살펴보도록 하겠다.
그리고 백트래킹은 대부분 DP나 dfs로도 풀 수 있을거같다?

우선 백트래킹의 기본은 재귀함수이다.

K개중 N번 선택하기

예를 들어 0 1이 있고 이들중 하나를 골라서 3자리수를 만든다고 하면, 우리는 첫번째자리수에 01 두번째에 01 세번째에 10 해서 총 2 2 2 = 8의 결과물이 나오게 된다.

이를 응용해서 풀면 되는데
000, 001, 010, 011 이런식으로 3개씩 고르고 만약 조건을 만족한다면 다시 return하고 정답에서 pop하는 방식으로 구현해야한다.

이 return 조건을 잘 써주는것이 백트래킹의 핵심이다.

이 문제의 핵심은 조건없이 k개중 n개를 뽑는것이다.

K 개중 하나를 N번 선택하기

위의 문제와 유사하지만, 이번 문제는 조건이 있는 뽑기를한다. 예를 들어 0 1 을뽑는데 0이 연속하지 않는 경우를 고른다거나 하는것이다.

두가지 접근방법이 있는데

1. 아예 다 뽑고 출력이나 처리과정에서 조건검사를 통해 제거하거나

2. 뽑을때부터 조건검사를 통해 안뽑는방법 두가지가 있다.

주로 몇개의 돌들이 점프해서 어디로 이동하고 이런문제가 있는듯하다.

N개중 M개 뽑기

수학에서 combination을 백트래킹으로 구현하는것이다.
이 경우는 보통 뽑아야하는 개수를 cnt, 뽑히는 수들을 curr_num으로 표현해서 구현한다.

def pick(curr_num, cnt):
	if cnt == m:
    	print()
        return
    if curr_num == n:
    	return
        
    ans.append(curr_num)
    pick(curr_num + 1, cnt + 1)
    ans.pop()
    
    pick(curr_num + 1, cnt)

다음과 같은 방식으로 주로 진행된다.

경우의 수를 두개로 나누어

1. 현재수를 뽑는 경우
   -> 수를 다음수로 넘기고, 뽑힌 숫자 개수도 하나 늘린체 재귀호출

2. 현재 수를 안뽑는 경우
   -> 수를 다음수로 넘기되, 뽑힌 숫자는 그대로

로 접근하여 해결한다.

유클리드 거리 문제

m 개만큼 점을 뽑고 그 점중 가장 먼점의 거리를 구한다음, 그 거리가 가장 작은 먼 점을 구하는 문제이다.

복잡해보이지만 점을 m개 만큼 뽑는 backtracking한번, 그리고 뽑힌 점들 사이에 2개씩 뽑아 거리를 측정하는 backtracking한번 총 2회 트래킹으로 문제를 풀면 된다.

N-queen

백트래킹하면 아마 n-queen문제가 가장 유명할거같은데 지금까지 풀었던 문제들이랑은 조금 맥락이 다르다. 나중에 해보도록 하겠다.