점 연결 퍼즐에 관한 내부 점 우선 연결 알고리즘 = An Internal Dots Priority Connection Algorithm for Dots Link Puzzle

다국어 초록 (Multilingual Abstract)

This paper proposed an algorithm that can obtain an accurate solution with linear time complexity of to a Dot Link Puzzle (DLP) that connects identical color, letter, or numeric dot pairs (2n) without intersection(or crossing). There is no known method of obtaining the solution of DLP other than the brute force search method of time complexity that connects dot pairs in an arbitrary order. This paper adopted an internal point-first connection and a border-adjacent point-later connection method. The proposed algorithm was first connected so that there was no intersection between dots existing inside the board. Finally, a dot pair adjacent to the board edge was connected by a curved line to a space that did not intersect with the lines conformed. As a result of applying the proposed algorithm to various benchmarking data, it was shown that the solution can be obtained with complexity.