초등학교 4학년 딸아이가 수학학원 문제를 내게 물으러 왔다. 딱 봐도 경우의 수가 많아서 손으로는 풀기가
힘들어 보였다. 선생님들도 쉽게 푸는 방법은 없을 것 같다. 혹시 있으시면 알려주세요....
자세히 보니 알고리즘으로 풀 수 있는 경우겠구나 싶어서 풀어 본 문제이다. 그래서
포스팅을 한 번 해본다. 다만 몇 분이나 이 글을 읽을지는 미지수이다. ^^
6*6 의 정사각형 map 에서 0,0 에서 시작해서 5,5 로 나가는 길을 찾아야 한다. 갔던 곳은 다시 방문하면 안되고
해당하는 행과 열의 방문횟수는 기준값과 꼭 일치 해야 한다. (아래 표에서 첫번째 행과 마지막 열에 표시)
물론 골인 지점과 정사각형의 크기는 변할 수 있다.
1
3
4
5
2
2
start
2
3
4
1
4
goal
4
처음에는 BFS 로 진행을 하려고 했지만 , 길을 만들 때마다 행과 열을 몇 번이나 지나갔는지 확인해서 기준이 되는 값보다 커지면 바로 리턴해야 되는 데, BFS 로 진행하면 몇 번 지나갔는지 기록해야 되는 변수가 많아야 되고 예측하기 힘들다고 판단해서 DFS 로 진행하기로 했다. DFS 로 진행하면 해당하는 행과 열에 변수 하나씩만 할당이 되면 된다. (calX, calY) DFS 는 stack 과 재귀가 있다. 나는 그중에서 재귀로 구현을 해봤다.
재귀 함수를 호출 하기 전에 행과 열을 방문한 횟수 및 방문 여부를 업데이트 하고 나올 때는 앞에서 업데이트 한 내용을
다시 원복 시켜준다. 이러한 내용은 DFS 관련 문제를 많이 풀다 보면 한번은 적용해보았을 기법이다.
추가적으로 이 문제는 딸 아이 숙제였기 때문에 길을 확인해야 하기 때문에 , 길도 기록해놓았다. 길은 단순한 Queue 로로 구현했고 , 정답일 때에만 , 즉 기준값과 일치 할 때에만 출력하게 만들어 놓았다.
행과 열을 방문한 횟수가 기준값보다 클 때에는 바로 return 하게 했는 데, 이는 지금 생각해보니 가지치기를 한 셈이 되었다. 물론 실제로 문제로 나와서 제한시간에 오버할 가능성도 없지는 않다. ^^.
for (int i = 0; i < INTEGER_NUM; i++) { nodes[nodes_cnt].children[i] = NULL; } nodes[nodes_cnt].isWord = false; return &nodes[nodes_cnt++]; }
void add(NODE* root, char* str) { NODE* c = root;
for (int i = 0; str[i]; i++) {
int nextIdx = str[i] - '0';
if (c->children[nextIdx]) { c = c->children[nextIdx]; } else { NODE* newNode = myalloc(); c->children[nextIdx] = newNode; c = c->children[nextIdx]; } } c->isWord = true; }
int find(NODE* root, char* str) { NODE* c = root;
for (int i = 0; str[i]; i++) { if (c->isWord == true) return 0;
int nextIdx = str[i] - '0';
c = c->children[nextIdx]; } return 1; }
void init() { nodes_cnt = 0; }
int canAdd() { int wordCnt; char inputStr[MAX_NUM][11]; NODE* root = myalloc();
cin >> wordCnt;
for (int i = 0; i < wordCnt; i++) { cin >> inputStr[i]; add(root, inputStr[i]); } for (int i = 0; i < wordCnt; i++) { if (!find(root, inputStr[i])) return 0; } return 1; }
