메일로 질문이 왔습니다. 코딩 테스트를 준비할 때, 하드 코딩을 하는 것은 별로 안 좋나요? 사실, 그에 대한 답은 제가 쉽게 답할 수 없었습니다. 하드 코딩을 하거나, 답을 미리 저장을 해 놓는 방법으로, 백준 내에 있는 문제를 푼 것이 10개에서 15개 내외밖에 되지 않기 때문입니다. 중요도가 떨어져 보일 수 있어요.

 

 이 기법을 쓰는 이유는 단 하나입니다. 정말 안 풀릴 때 최후의 수단으로 써 보라고. 제가 이 기법을 쓰지 않았다면, 10개에서 15개 정도 되는 문제를 풀지 못했을 겁니다. 오늘은 '답을 미리 저장해 놓는 기법' 을 구현 문제에 어떻게 쓰일 수 있는지 보도록 하겠습니다. 백준 17825번 문제인 주사위 윷놀이를 보도록 하겠습니다. 문제가 상당히 길기 때문에, 제가 링크를 걸어 놓겠습니다.


 다 읽어 보셨나요? 어떻게 미리 db를 구축해 놓으면 좋을까요? 문제를 읽어보셨다면, 제일 까다로운 부분이 어떠한 칸에서 k번만큼 이동하면 어떤 칸에 도착하는지를 알아내는 게 제일 어렵다는 것을 알 수 있습니다. 이 부분만 db로 해결해 보도록 하겠습니다.

 

 윷놀이 판은 외곽 부분과 내부 부분으로 나눌 수 있음을 알 수 있습니다. 외곽 부분은 시작에서 남쪽, 다시 10에서 동남쪽, 20에서 북동쪽, 30에서 북서쪽, 40이 써져 있는 판, 그리고 도착으로 이루어지는 부분을 의미합니다. 그리고 내부 부분은 외곽이 아닌 부분을 의미합니다. 이 둘로 나누는 이유는 발판의 넘버링을, 조금 더 쉽게 하기 위함입니다.

 

 

 저는 이렇게 넘버링을 했습니다. 여기서 외곽 부분을 연두색으로 칠해보겠습니다.

 

 

 그러면 외곽인 것들 중에서, 5의 배수인 것들 빼고는 공통적인 규칙이 보일 거에요. k번 칸으로부터 x 만큼 이동하면, k + x에 도달한다는 것입니다. 물론, 16, 17, 18, 19, 20번은 예외라면 예외겠군요.

 

 

 그러면 연두색으로 칠해진 것 중에서 5의 배수인 것과, 연두색으로 칠해져 있지 않은 것에 대해서는 어떻게 하면 되나요? x칸 갔을 때의 값을 미리 저장해 놓으면 됩니다. 최대 5칸까지 이동이 가능하니, db[x][k]를 x에서 출발해서 k까지 갔을 때, 몇 번 칸에 도착하는지로 정의하면 됩니다. 사실 이 처리를 하는 이유는, 특정 칸에서 출발을 하는 경우와, 통과하는 경우 어느 방향으로 가는지 일일히 구현하려면 굉장히 까다롭기 때문입니다.

 

 

 먼저, 현재 칸 i로부터 0칸을 이동하면 i이므로, 32번 칸까지 모두 돌면서, i번 칸에서 0칸을 이동하면 i번 칸에 도달한다는 정보를 적습니다. init_go를 호출하기 전에 db[i]는 비어 있기 때문에, 70번째 줄에서 push_back을 해 주면, db[i][0]의 값은 i가 될 겁니다.

 

 

 다음에 add(cur,a,b,c,d,e)를 호출하는데요. cur로부터 1칸을 가면 a, 2칸을 가면 b, 3칸을 가면 c, 4칸을 가면 d, 5칸을 가면 e에 도착한다는 것을 의미합니다. 이것 또한 직접 해 보면서 알아내야 하는 부분입니다.

 

 

 add 함수에서는 a, b, c, d, e를 차례대로 벡터 db[cur]에 추가합니다. 다음에 x번에 도착했을 때, 획득하는 점수를 저장하기 위한 배열을 하나 선언합니다. sc[x]에 들어가는 값은 x번 칸에 도착했을 때, 얻는 점수를 의미합니다.

 

 

 외곽 부분은, 번호가 x인 노드에 도달했을 때 점수는 2x입니다. 그렇지 않은 칸들에 대해서 일일히 초기화를 해 줍니다. 칸의 갯수가 40여개 정도밖에 되지 않기 때문에, 그냥 하드 코딩을 해서 db를 만들어도 됩니다. 그러면 이렇게 db를 만들어 두면 뭐가 좋을까요? 문제는, 말 4개가 있고 말들을 조건에 맞게 10번 이동시켰을 때, 점수를 최대화 하는 문제입니다.

 

 

 그러면 각 턴마다 1, 2, 3, 4번 말 중 하나를 택해서 move를 하면 되니, 이 부분은 back tracking으로 처리하면 됩니다. process 함수를 봅시다.

 

 

 말이 4개 있습니다. 그렇기에, i번 말이 있는 위치와, 각 노드에 몇 개의 말이 있는지를 체크할 겁니다. 어짜피 말이 이동한 경우에, 출발점인 0번에 도달하지는 못합니다. 그러니, 도착할 예정인 곳이 32이거나, 도착할 예정인 곳에 말이 없다면 이동해 주면 됩니다. 이 부분을 어떻게 처리했는지 보겠습니다.

 

 

 next_pos는 내가 선택한 말이 1턴을 수행했을 때, 어느 위치로 갈 예정인지를 알려주는 변수입니다. 이 next_pos를 단 1줄만에 채울 수 있었습니다. db[cur_pos][su]로요. su는, 몇 칸을 이동시킬 것이냐를 나타내는 변수였습니다. 그리고 cur_pos는 말이 이동하기 전에 position이였습니다.

 

 당연하게도, 가짓수가 많은 이 문제의 경우, next_pos를 db 없이 깡으로 구한다고 했다면 끔찍할 정도로 구현량이 많았을 거에요. 하지만, 적당히 db에 넣었기 때문에, 이 부분을 간단하게 처리할 수 있었습니다. 전체 코드는 17825.cpp를 보시면 됩니다.

 


 더 좋은 넘버링 방법이 없을까요? 주사위는 많아봤자 10번 던질 수 있습니다. 그렇다면 20번 칸에서 5칸 이동을 10번 해 봤자, 70번 칸으로 이동을 하지 않을까요? 넉넉하게, 외곽 노드와 출발, 도착 노드는 1번부터 100번까지 번호를 매기고, 내부 노드는 101번부터 120번까지 매기면 됩니다.

 

 

 그 다음에는 어떻게 처리하는 게 좋을까요?

 

 

 도착 지점을 21, ... , 100이라고 두고 이 지점에 도달했을 때 k칸 이동하면 x + k다. 라는 정보를 db에 넣어두면 됩니다. 예를 들어, db[21][3] = 24이고, db[100][5] = 105. 이렇게 넣으면 되겠습니다. 그런데, 105번은 내부 노드 번호이지 않냐고 물어보실 수 있습니다.

 

 생각해 보면 틀린 이야기는 아닙니다. 그런데, 20번에서부터, 5칸씩 10번 이동해봤자 70입니다. 사실상 71번, 72번, ... , 100번은 도달할 리가 없기 때문에, 아무렇게나 넣어도 됩니다.