[알고리즘] 개미집 찾기 문제 (한 node가 다른 node 의 탐색 경로 내 존재 여부 찾기)

1. 문제 정의

root가 개미집

root에서 개미가 출발

어떤 node(여기서는 intersection으로 명명) 밑으로는 모두 먹이가 있음

이런 노드를 특이한 교차로(singular intersection)라고 함

이런 특이한 교차로가 2개 주어짐

이 2개의 특이한 교차로 중 하나가 다른 하나의 path에 포함되는지 여부 판별

2. 문제 풀이 (using Set class)

     예전에 구현했던 집합(Set) template class 사용

struct val_pair { uint32 left; uint32 right; }; struct singular_pair { uint32 left; uint32 right; }; typedef struct { struct val_pair *val_pairs; uint32 nu_inputs; struct singular_pair *singular_pairs; uint32 nu_singulars; } input_t; struct val_pair input_val_set[] = { {1, 2}, {2, 4}, {2, 5}, {1, 3}, {3, 6}, {3, 7}, {3, 8}, }; struct singular_pair check_val_set[] = { {1, 5}, {4, 7} }; struct val_pair input_val_set2[] = { {1, 2}, {1, 3}, {3, 4}, {3, 5}, }; struct singular_pair check_val_set2[] = { {2, 3}, {3, 5} }; input_t inputs[] = { {input_val_set,  7, check_val_set,  2}, {input_val_set2, 4, check_val_set2, 2}, }; void check_the_union_way() { int set_idx1, set_idx2, idx; uint32 i, j, k; Set<uint32> *set; for (i = 0; i < get_length(inputs, inputs[0]); i++) {   set = new Set<uint32>; for (j = 0; j < inputs[i].nu_inputs; j++) { set_idx1 =                set->findIndex(inputs[i].val_pairs[j].left); if (set_idx1 < 0) set_idx1 =                 set->addSet(inputs[i].val_pairs[j].left); set_idx2 =                set->findIndex(inputs[i].val_pairs[j].right); if (set_idx2 < 0) set_idx2 =                 set->addSet(inputs[i].val_pairs[j].right); set->unionToLeft(set_idx1, set_idx2);   }   set->traverseAll(ce1401_visit_func);   for (k = 0; k < inputs[i].nu_singulars; k++) { idx =          set->isParent(inputs[i].singular_pairs[k].left,                           inputs[i].singular_pairs[k].right); cout<<"ret = "<<(idx != -1 ? 1 : 0)<<endl;   }   delete set; } }

output