코딩테스트에 나올 만한 백트래킹 쉽게 정복해 봅시다.

 구현, 백트래킹은 코딩 테스트에서 많이 나오는 단골 주제 중 하나입니다. 물론 tree dp나, segment tree하고 조합론을 아름답게 섞어놓은 dp도 나오기는 하지만. 중요도가 상대적으로 높지 않습니다. 그 말인 즉슨, 포기할 건 포기하더라도, 다른 사람들이 다 풀 수 있는 기본부터 챙겨 가자는 의미입니다. 그 기본 중 하나는 백트래킹입니다.

 

---

 새로 추가된 문제인 18290번과 18292번 문제 NM과 K 시리즈를 보겠습니다. 개인적으로 적당히 난이도가 있으니, 입문 문제로는 좋은 듯 싶습니다. 문제는 아래와 같습니다.

 

 조건을 잘 읽어보시고, 어떻게 풀어야 할 지 잘 생각해 보세요. 18292는 K 조건이 다른데요. K가 구간 [1, min(50,NM)]에 속하는 정수이다. 라는 것만 다릅니다. 그 문제는 머릿속에서 지우시면 됩니다. 시도를 해 보시겠다면, 먼저 1648번을 푸시는 것이 현명합니다. 생각을 해 보셨나요?

 

18290번은 K가 작습니다. 그렇다면, 최악의 경우에 100 x 99 x 98 x 97 < 1억. 시도해 볼 만한 가치가 있어요. 그런데, 10^8이 대략 1억이기 때문에, 각 가짓수에 대해서 O(1)에 처리하기는 해야 하고. i번째 행, j번째 열의 고유 번호를 Mi + j로 잡아 봅시다.

 

 

 그러면 입력을 받을 때도, 2차원 배열이 아니라, arr과 f를 1차원 배열로 처리하겠다는 이야기인데요. 여기까지는 그리 어렵지는 않아 보입니다. 그런데 왜 굳이 이렇게 처리하느냐고 묻냐면, 아래로 갈수록, 행이 같다면 우측으로 갈수록 고유 번호가 증가하기 때문입니다. 그러면 K개의 칸을 선택할 때, 고유 번호가 a(1), ... , a(K)라 합시다. 이 때, a(1), ..., a(K)는 모두 다른 수입니다. 다른 칸을 선택했으니 그럴 수 밖에 없어요.

 

 그러면, 번호가 제일 작은 칸부터, 순서대로 선택한다. 는 전략을 세워도 될까요? 예를 들어 N = 2이고 M = 3이라고 하고 K = 3이라 해 봅시다. 그러면 아래와 같이 고유 번호가 매겨질 거에요.

 

 

 이 중 3개의 서로 다른 칸을 선택했다고 해 봅시다.

 

 

 노란 색이 선택한 칸입니다. 그러면 0번, 2번, 4번 순서대로 select 했더니 요렇게 되더라. 라고 해도 될까요? 이것이 핵심입니다. 즉, i번 칸을 택하면, 그 다음 턴에는 [i+1, NM)번 칸 중에 하나를 선택하면 됩니다.

 

 

 예를 들어, 0, 2번을 선택한 경우에, 그 다음 턴에 3번, 4번, 5번 중 하나를 선택하면 됩니다. 그런데, 조건이 하나 걸려있는 게 문제입니다. 선택한 칸들 중에 인접한 것들이 없어야 한다.

 

 

---

 우리는 작은 것부터 큰 것 순으로 볼 겁니다. 그러면, 현재 어떠한 칸을 선택할 때, 선택이 된 이전 것과 인접하는지 검사하라면, 위에 방향과 왼쪽 방향만 보면 된다는 것을 알 수 있습니다. 예를 들어서, 3번을 보겠습니다.

 

 

 어떤 것만 검사하면 되나요? 윗 방향과 왼쪽 방향만 보고 있다는 것을 알 수 있어요. 그런데 사실 3은 또 왼쪽을 볼 필요 조차 없습니다. 가장 좌측에 있는 열이기 때문입니다. 우측과 아랫쪽은 볼 필요가 없을까요? 제가 작은 것부터 select 하는 전략을 취했기 때문에, 그럴 필요가 없습니다. 아랫쪽으로 이동하거나, 우측으로 이동하면 수가 커지는 것을 의미하는데요.

 

 만약에 3번을 검사하는데, 4번이 select가 되어져 있다면 4번 다음에 3번을 택할 수도 있다는 의미가 되거든요.

 

 

 따라서 기준 위치가 있을 때, 왼쪽과 윗쪽을 보는데요. LEFT 방향은 열이 1열일 때 부터 의미가 있습니다. 0열 왼쪽에는 아무것도 없기 때문에 고려하지 않아도 됩니다. 다음에 UP은 어떤가요? 0번째 행일 때 의미가 있나요? 없습니다. 따라서, 1번째 행인 것부터 보면 됩니다.

 

 con[x]는 x를  선택하려고 했을 때, 어떤 칸이 선택되지 않아야 하는가? 를 의미합니다. 예를 들어 x = 0이라면, 필요 없습니다. x가 1이라면 0번이 선택되지 않아야 합니다. 이렇게 전처리를 하면 백트래킹 함수는 생각보다 쉽게 작성하실 수 있습니다.

 

 

---

 먼저, nm개의 칸을 돌면서 어떤 칸을 먼저 선택해 봅시다.

 

 

 그러면 이 때, 선택된 칸에 적혀져 있는 수의 합은 arr[i*m+j]가 됩니다. 그리고, i*m + j번째 칸을 선택한 것이 되고, 선택한 칸의 갯수는 1이 됩니다. 이제 work 함수의 내부를 보도록 하겠습니다.

 

 

 depth는 현재 선택된 칸의 갯수입니다. 이 값이 k와 같다면 빠져 나와야 합니다. 적절히 처리해 주고 나오면 됩니다. 그렇지 않다면, 마지막에 선택한 칸의 번호가 lo이기 때문에, lo + 1부터 nm까지 번호가 적혀있는 칸 중에 하나를 선택하면 됩니다. 그런데 상하 좌우로 인접한 칸이 있으면 안 되는 조건이 있기 때문에..

 

 chk 함수로, i번째 칸을 선택해도 되는지를 판단합니다.

 

 

 cur번째 칸을 선택하려면, con[cur]에 속해있는 칸들이 선택이 되어 있는지 보아야 합니다. f[con[cur][i]]가 1이라는 의미는, cur번째 칸과 위, 왼쪽 방향으로 인접한 칸이 이미 선택이 되었다는 것입니다. 이 경우, 1을 리턴합니다. 49번째 줄에 chk 함수의 리턴 값이 1이면, continue를 하는데요. i번째 칸을 택했을 때 invaild 하면 선택하지 않고 다른 칸을 선택합니다. 전체 소스 코드는 링크에 있습니다.

 

 

---

 추가적인 opt를 고민해 봅시다. 사실 우리는 100^4의 복잡도로 풀었습니다. 그런데 잘 생각해보면, 100 하나는 뗄 수 있다는 것을 알 수 있습니다. 100을 10으로 뗄 수 있는데요. 즉 100^4를 10x100^3으로 줄일 수 있다는 이야기입니다. K = 4라고 하고, N = 3, M = 5라고 해 봅시다.

 

 

 0번, 2번, 6번을 선택했습니다. 그 다음에 선택해야 할 칸은 어떻게 판단하면 좋을까요? 그 전에 보라색 부분은 아무거나 선택해도 된다는 것을 알 수 있습니다. 보라색 부분은 연속적인 구간으로 나타낼 수 있습니다. 그렇기 때문에, [i, nm-1]까지의 칸들에 들어 있는 수들 중 최댓값을 전처리 한다면, 보라색 부분에 대해서는 굳이 탐색하지 않아도 O(1)만에 구할 수 있습니다.

 

 N = 5이고, M = 5라고 하고, 0, 2, 6번을 택한 경우에는 어떨까요?

 

 

 보라색 부분에 있는 칸 중에서, 노란색으로 칠한 칸과 인접한 것이 있나요? 없습니다. 따라서, 보라색 부분과 군청색 부분으로 나누어서 탐색할 수 있습니다. 군청색 부분은 가능한지 불가능한지 따져가면서 탐색하면 됩니다. 보라색 부분은 무조건 되기 때문에, 구간 최댓값, 최소값 전처리가 되어 있다면, 보라색 부분 전체를 탐색하지 않아도 됩니다. N과 M은 커 봐야 10이기 때문에, 최악의 경우라도, 전처리가 되어 있다면, O((NM)^4)가 아닌, O(N^3M^4)만에 탐색할 수 있습니다.

 

 이러한 아이디어는 백준 1648번 격자판 채우기에서도 적용이 되니 알아두셔도 좋을 듯 싶습니다.