미로 탐색 : 최단 경로 찾기

최단 경로 찾기 방법

우선법 진행 과정의 좌표 리스트를 저장한다.

저장된 좌표 리스트에서 중복되는 좌표 부분을 잘라낸다.

-> 다시 되돌아 오기 위해선 반드시 갔다 오는 중복된 지점이 존재하기 때문에 중복된 지점 사이에 있는 경로를 지워도 문제 되지 않음.

// 최단 경로를 일차원 배열에 x,y 순으로 차례로 넣는다.
// 마지막은 -1, -1로 한다.

void Maze::ShortestPath(){

    int i,j = 0;
    int x,y;
    int x1,y1;
    
    while(m_arrayRecord[i] >= 0){
    
        x = m_arrayRecord[i];
        y = m_arrayRecord[i+1];
        j = i + 2; // 한 좌표가 두개의 정수이기 때문에 다음 좌표는 +2이다.
        
        while(m_arrayRecord[i] >= 0){
        
            x1 = m_arrayRecord[i];
            y1 = m_arrayRecord[i+1];
            if(x == x1 && y == y1) j = DeletePath(i,j); // 같은 좌표가 발견되면 중복 경로를 삭제해라
            j += 2;
        }
        i += 2;
    }
}