quento 퍼즐 문제 : 백 트래킹으로 풀어봅시다.

 안녕하세요. chogahui05입니다. 인성에서 100%의 확률로 떨어지다 보니 제 인성에 문제가 있는 듯 싶어요. 셀프 깍기는 밴이고요. 오늘은 좀 유명한 게임을 다뤄볼 것인데요. quento라고, n개의 숫자와 n-1개의 연산자를 조합해서 특정한 수 m을 만들어야 합니다. 이 때, 한 번 방문한 칸은 다시 방문할 수 없고, 인접한 칸으로만 이동이 가능합니다.

 

 

 예를 들어 봅시다. 7 밑에 네모가 2개 있어요. 이는 수는 2개, 연산자는 하나를 사용 해야 한다는 이야기입니다. 그러면 (0,0)에서 출발해서 오른쪽으로 가면 될 거에요. 5 + 2 = 7이기 때문입니다.

 

 

 이번에는 11을 만들어야 하는데요. 사용해야 하는 숫자의 갯수는 3개, 연산자는 2개입니다. 7+4도 답은 됩니다. 하지만, 사용한 숫자의 갯수가 2개밖에 되지 않아요. 9 + 4 - 2는 어떤가요? 3개의 수를 사용했고, 심지어 경로가 만들어 집니다. 방문한 곳을 다시 재방문 하지도 않고요. 대충 QUENTO 퍼즐의 규칙을 아셨나요? 백준 10429번 문제는 사용해야 하는 수의 갯수가 주어졌을 때, m을 만들 수 있는지 물어보는 문제입니다. 물론 퍼즐은 3 by 3 크기이고요.

 

 

---

 쉽지 않지만, 차근 차근 해결해 보도록 하겠습니다. 먼저 우리는 수가 있는 검정색 칸에서 출발해야 합니다. 검정색 칸의 특징은, i행 j열이라고 할 때, (i+j)가 2로 나누어 떨어진다는 것입니다.

 

 

 그러면 main 함수는 어떻게 작성하면 좋을까요? i+j가 2로 나누어 떨어지지 않으면 continue를 하고, 그렇지 않다면, 해당 위치부터 back_tracking을 돌리면 됩니다. 저는 이 함수를 dfs라고 했네요. 만약에 후보해가 있으면 함수 내에서 exit 함수를 호출하고, 그렇지 않으면, 34번째 줄에서 해가 없다고 출력을 합시다.

 

 그러면 dfs 함수의 내부는 어떻게 구성해야 할까요?

 

 

 그 전에, 이 상황 먼저 생각해 봅시다. (0,0)에서 출발해서 (0,1), (1,1), (2,1)을 거쳤습니다. 이 때 문자열에는 "5+4+"가 저장이 되어야 할 겁니다. 그 다음에 9로 갔다고 생각해 봅시다. 그러면 string에는 "5+4+9"가 저장이 될 겁니다. 만약에 숫자가 3개고, 연산자가 2개인 조건을 만족했다면, string에 있는 수식을 계산해야 할 겁니다. 이를 eval 하는 기능이 필요하지 않을까요?

 

 

 이것은 생각보다 깔끔하게 작성이 가능합니다. 일단, ans를 문제의 문자열 "9+5+4"라고 해 봅시다. 그러면, 일단 ans[0]을 먼저 읽어야 함은 자명합니다. 그런데 숫자를 읽었을 때, '9'는 9가 아닙니다. 48 + 9입니다. '0'의 아스키 값이 48임을 이용하면, 우리는 처음에 ans[0] - '0'을 저장해야 함을 알 수 있어요. 68번째 줄에 그러한 일을 수행하고 있어요.

 

 그리고 i = 2부터 보면 되는데요.

 

 

 현재 i가 2라면 '5'를 가리킬 겁니다. 그러면 5를 더하거나 빼야 한다는 것은 자명합니다. 그런데 이것을 어떻게 판단해야 할까요? 바로 이전의 문자가 '+'인지 '-'인지만 보면 됩니다. 만약에 '+'라면 더하는 것이고, '-'라면 빼야 하는 겁니다.

 

 

 바로 이전 것을 보니까 '+'였습니다. 따라서 5를 res 값에다가 더해야 합니다. 그리고 나서 무엇을 봐야 할까요? 그 다음 숫자는 2번째가 아닌 4번째에 있습니다.

 

 

 그러니 i는 2만큼 증가해야 합니다. 이걸 문자열의 끝에 도달할 때 까지 반복해 주면 됩니다. 문자열 "2+3-4" 꼴로 들어오는 것에 대해서 evaluate 하는 chk를 작성하였습니다.

 

 

---

 그러면, 이제 무엇이 남았을까요? dfs, 즉 백트래킹 함수를 작성하는 것입니다. 그 전에, 우리는, m을 만들 수 있을 때, 어떻게 터치를 해야 하는지를 출력을 해야 합니다. 그것을 저장하기 위해서, vector를 하나 선언합니다. 다음에 방문한 곳을 다시 재방문 하면 안되니까, 어떠한 point를 방문했는지 체크하는 visit 배열도 선언합니다. 그리고 "5+3+7"과 같이 eval을 계산하기 위한 문자열을 저장하기 위한 string도 선언합니다.

 

 

 그리고 인접 방향을 탐색하기 위해서 dx와 dy도 선언했습니다. 그러면 dfs 함수에서는 어떻게 하면 좋을까요?

 

 

 (x,y)를 방문했을 때, 방문했다는 처리를 하고, 방문을 끝냈을 때, 그러니까 함수가 끝날 때, (x,y)를 방문하지 않았다는 처리를 해야 할 겁니다. (x,y)에 도달했을 때, ans[d]에 str[x][y]를 집어 넣습니다. 그리고 visit[x][y]는 1로 set 하고, 좌표 정보를 v에 push합니다.

 

 함수가 끝날 때는 역으로 하면 될 거에요. 46번째 줄이 그 처리를 합니다. 그러면 방문 처리를 했을 때, 어떠한 work를 해야 한다는 것을 알 수 있는데요.

 

 

 이 부분은 크게 2개로 나눌 수 있어요. 수 m개가 다 채워진 경우. 그렇지 않은 경우로 나눌 수 있는데요. m개가 채워진 경우에는 44번째 줄을 수행합니다. 이 때에는 m이 3인 경우, "3+7+4"가 n과 같은지 등을 확인하면 됩니다. 만약에 같다면, v에 저장이 되어 있는 경로를 출력하고 종료하면 됩니다. 그렇지 않으면, (x,y)를 방문했다는 정보와 경로 정보에서 (x,y)는 제거해야 합니다.

 

 

 그렇지 않다면 어떻게 하나요? 인접한 곳들을 탐색하면서 이미 방문했는지 등을 검사합니다. 방문했다면 continue, 그렇지 않다면, 인접한 곳을 다시 탐색하면 됩니다. 전체 코드는 제 github의 BOJ 탭에 올려놓았습니다.