마이크로 마우스 - 미로 시뮬레이션 프로그램 - 분기점(Node)- 탐색 알고리즘

탐색 알고리즘에 중에 내가 생각하고 반영중에 있는 것이 분기점(Seperate Point ) 탐색(Scan)  다른 말로 Node(노드) 알고리즘이다.
우리가 알고 있는 네비게이션 개념과 비슷하다고 할까? 동일하다고 할까? 네비게애션 알고리즘을 배우지 않아 모르겠지만 비슷할 것으로 생각한다.

기본 마우스 이동은 Home(시작점) -> 첫번째 분기점까지는 그냥 찾아서 오면 된다.
이때부터, 좌수법 이니, 뭐지 한다. 미로 탐사때만 사용하는 알고리즘으로 생각하면 된다.
분기점은 2가지이다. 4방향이 모두 열린것, 3방향이 열린것,
나머지 1방향만 열린 곳( 막다른 길)과 2방향 열린 곳( 그냥 지나가는 길)

길을 찾을 때 분기점을 기준으로 모두 검색을 하면, 미로 탐색이 마무리 된다. 분기점을 통해서 지나가지 않는 길은 마우스가 들어갈수 없는 길이므로 미로의 크기에 관계없이. 미로 탐색이 가능하다.

그림으로 그리면 쉽게 설명할 수 있겠지만, 내가 블러그 사용 법을 너무 잘 몰라 글로 마무리 한다.

분기 점 과 분기 점 사이를 1개의 끈 이라고 생각하면, 3개의 분기점이 있는 곳은 3개의 끝이 있고, 4개의 분기점이 있는 곳은 4개의 끈이 있다.
2개 방향이 열긴 곳은 그냥 끈이 되버린다.
막다른 길은 끈이 짤린 것이라.막다른 길에서 부터 분기점까지는 끈이 없는 것과 마찬가지이다.
이 분기점의 조합을 하면, 그냥 단숨에 미로 찾기가 끝나 버린다.

단 여기서 Goal (목적지)는 어디에 있는지 찾아야 한다. 목적지 를 찾으면 가장 가깝꺼나, 목적에 빨리 도달할 수 있는 분기점을 찾으면 목적지까지 쉽게 갈 수 가 있다.
집(Home)은 첫번째 분기 점까지 오면 바로 집이다.

분기점을 몇개를 거쳐서 갈 것인지를 고민하는 것이 분기점 탐색 알고리즘의 중요부분이다.

 

아래에 가면  미로 탐색 알고리즘에 대해 이야기 된 것이 있다.

https://namu.wiki/w/%EB%AF%B8%EB%A1%9C%ED%83%90%EC%83%89%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

미로탐색 알고리즘 - 나무위키

 

오늘은 여기까지 하고 추가 내용이 있으면 계속해서 끄적일 것이다.