20221114 TIL 백트래킹 알고리즘

 

오늘은 N-Queen문제를 풀어봤다.

https://school.programmers.co.kr/learn/courses/30/lessons/12952?language=java 

 

뭔가 풀릴듯 말듯 풀리지 않은 채로 시간이 너무 많이 흘러서 일과 시간을 지키기 위해 일단 풀이를 찾아봤다.

풀이들이 모두 백트래킹 알고리즘이라는 용어를 사용하고 있었고,

이 문제를 풀려면 백트래킹 알고리즘을 먼저 이해해야 될 것 같아서 백트래킹 알고리즘에 대해 알아봤다.

 

백트래킹 알고리즘은 모든 가능한 경우의 수를 고려해서 문제를 푸는 방식이다.

가능한 솔루션이 여러 개일 때 그 모든 솔루션을 다 구하는 경우에 사용한다.

N-Queen문제는 조건을 만족하는 가능한 모든 솔루션의 개수를 구해야하기 때문에

백트래킹 알고리즘을 사용할 수 있는 대표적인 문제이다.

 

decision choice가 있고, decision은 특정한 방식으로 제한되고, 특정한 목적을 달성했을 때 반환한다.

보통 재귀를 통해 구현할 수 있다.

https://www.youtube.com/watch?v=Nabbpl7y4Lo&t=516s

이 때 위와 같은 템플릿으로 재귀 함수를 작성하면 된다.

Backtrack이라는 함수는 결과값인 res와 여러 인자를 받는 재귀함수이다.

솔루션을 찾으면 res에 추가해줘야하기 때문에, 솔루션에 해당하는 조건을 GOAL REACHED에 작성해준다.

그리고 그 조건문에서 res에 찾은 솔루션을 넣어준다. 

이 때 솔루션은 Backtrack 인자를 통해서 넘어올 것이다.

 

매 재귀함수를 호출할 때 가능한 모든 경우를 CHOICES라고 하면,

그리고 백트래킹은 가능한 모든 경우 수를 확인하는 것이기 때문에 가능한 모든 경우의 수를 세서 NB_CHOICES에 넣고,

각각의 CHOICE가 조건을 만족하는지 확인을 해서 만족하는 경우에 CHOICE를 반영하고,

반영한 인자를 넣은 Backtrack함수를 호출하고,

CHOICE를 반영한 것을 다시 되돌려놓는다.

반영했던 것을 다시 되돌려 놓는 것은 다음 CHOICE를 실행할 때 앞의 CHOICE가 영향을 주면 안되기 때문이다.

 

Backtrack함수를 수행하면 res에 원하는 솔루션들이 모두 포함된다.

 

불변성을 토대로 코드를 최대한 작성하다가 백트래킹 함수에서 기존값을 이용하는 방식으로 작성을 했더니 매우 어색하고,

불변성 있게 코드를 짜고 싶은 마음이 샘솟는다...

기존 값을 변경하는 것이 매우 마음에 걸린다.

하지만 내가 아직 잘 모르니 다음에 백트래킹 문제가 나오면 일단 이 템플릿에 따라 작성을 해야겠다.

GOAL, CHOICE, CONSTRAINTS에 집중해서 풀면 된다!

그리고 불변성 있게 코드를 짜는 방법도 꼭 고민해보자.