한글내용
(Korean Abstract) |
x축 방향으로 원점을 떠나 x축 또는 y축에 평행한 방향으로만 격자점 간을 이동하며 자기 자신과 만나지 않는 경로를 '직교 경로(rectilinear chain)'라고 부른다. 모든 직교 경로는 왼쪽과 오른쪽으로 방향 전환이 이루어지는데 그 순서에 따라 L(left)과 R(right)로 이루어진 문자열에 일대일 대응된다. 이 논문은 L과 R로 이루어진 길이가 1 이상인 문자열을 입력받았을 경우, 해당 문자열에 대응되는 직교 경로에 대해서 그 도착점이 x축, -x축, y축, -y축에 도달할 수 있는지 판정하는 알고리즘을 제시한다. 특별히 입력받은 문자열의 L의 개수와 R의 개수의 차가 2개 이하일 경우에 대해선 직교 경로가 x축, -x축, y축, -y축 중 어느 한 축에 도달 가능한 점과 원점 사이의 거리값의 상한과 하한을 제시한다.
|
