| 요약 |
본 발명은, 주어진 격자행렬 G(열수 R, 행수 C)의 모든 격자의 상태를 이너 그리드로 지정하는 단계; G[*][0], G[*][C-1], G[0][*], G[R-1][*]의 격자를 선입선출 리스트인 큐(queue)에 삽입하는 단계; 선입선출 리스트인 큐(queue)에서 가장 먼저 삽입된 격자를 꺼내는 단계; 선입선출 리스트인 큐(queue)에서 꺼낸 격자 위에 적치된 블록이 있는지 판단하고, 있다면 선입선출 리스트인 큐(queue)에서 꺼낸 격자를 아웃터 그리드로 지정하고, 선입선출 리스트인 큐(queue)에서 꺼낸 격자의 8-이웃(neighbor) 격자 중 기존에 추가된 적이 없는 격자를 선입선출 리스트인 큐(queue)에 삽입하는 단계; 선입선출 리스트인 큐(queue)에서 꺼낸 격자 위에 적치된 블록이 없다면 선입선출 리스트인 큐(queue)에서 꺼낸 격자 위에 벽이 있는지 판단하여, 벽이 없다면 선입선출 리스트인 큐(queue)에서 꺼낸 격자를 오픈 큐(Open queue)에 추가하고 벽이 있다면 선입선출 리스트인 큐(queue)에서 꺼낸 격자를 아웃터 그리드로 지정하는 단계; 선입선출 리스트인 큐(queue)에 남은 항목이 있는지 판단하여, 남은 항목이 없다면 오픈 큐에 가장 먼저 삽입된 격자를 오픈 큐에서 꺼내는 단계; 오픈 큐에서 꺼낸 격자 위에 출구가 있는지 판단하여, 없다면 오픈 큐에서 꺼낸 격자의 8-이웃 격자에 오픈 그리드인 격자가 있는지 판단하고, 있다면 오픈 큐에서 꺼낸 격자 위에 블록이 있는지 판단하는 단계; 오픈 큐에서 꺼낸 격자 위에 블록이 없다면 오픈 큐에서 꺼낸 격자를 오픈 그리드로 지정하고, 8-이웃 격자 중 기존에 추가된 적이 없는 격자를 오픈 큐에 삽입하는 단계; 오픈 큐에서 꺼낸 격자 위에 블록이 있는 경우, 오픈 큐에서 꺼낸 격자 위에 벽이 있는지 판단하여, 있다면 오픈 큐에서 꺼낸 격자를 아웃터 그리드로 지정하고, 없다면 오픈 큐에서 꺼낸 격자를 바운더리 그리드로 지정하는 단계; 및 오픈 큐에 남은 항목이 있는지 판단하는 단계를 포함하는 격자 기반 공간 파악 방법을 제공한다.블록, 그리드, 적치, 오픈, 바운더리, 아웃터, 이너
|
