알고리즘 공부-3 (미로탐색)

오늘도 전에 올린 알고리즘 공부에 이어서, 미로탐색 알고리즘에 대한 내용을 공부해보았습니다.

아래는 오늘 공부한 내용을 요약한 노트입니다.

또 말씀드리지만, 저번과 마찬가지로 잘 정리가 안된 포스팅입니다. 양해부탁드립니다.

배열

  • 정의 : 연속된 메모리 공간을 차지하는 같은 타입의 테이터 집합입니다.

정적 테이터타입으로 그 크기도 미리 정해져있습니다.

배열의 인덱스 사용은 사용자 책임입니다. (배열의 크기에 벗어나면 컴파일 오류는 안나지만, 실핼시 오류는 발생하기 때문입니다.)

또한 인덱스는 0부터 크기-1까지이고, 배열 자체에 크기를 알 수 있는 방법이 없습니다.

  • 사용법 : 테이터형 배열명[배열 크기];

참고로 배열의 이름은 시작점을 가리키고 있습니다.

c++ 코드로 아래와 같이 사용할 수 있습니다.

int iarray[10]; // 배열 선언만
int iarray[3] = {}; // 배열 선언과 초기화
int iarray[3] = {1,2,3}; // 배열 선언과 개별 초기화

배열을 선언만 할 수도 있고, 초기화도 같이 할 수 있습니다.

배열과 포인터 관계

배열의 이름은 배열이 저장된 메모리의 선두를 가리키는 상수(constant) 포인터입니다. 그래서 상수 포인터이므로 딴 배열을 가리킬 수 없습니다.

다만 다른 포인터를 생성하여 배열을 가리킬 수 있습니다.

아래와 같이 c++ 코드로 작성할 수 있으며,

*(array + 3) == array[3] // 같다

포인터처럼 사용이 가능하기 때문에 array의 처음을 가르키는 포인터에 +3해서 3번째 값에 접근할 수 있습니다.

함수에서 1차원 배열 사용

c++에서 배열은 크기정보가 없습니다. 그러므로 배열의 끝에 특정 값을 넣는 방법이나 배열의 크기를 따로 지정하는 방법을 씁니다.

  • c++ char 문자열은 끝에 null값을 넣는 방식으로 구현되어 있습니다.

다차원 배열

  • 정의 : 인덱스 연산자([])를 차원 수만큼 씁니다.

array[2][2]는 array[0]과 array[1]이 각각 두개짜리 정수 배열을 가리킵니다.

함수에서 다차원 배열 사용

그냥 인자로 넣으면 1차원 배열로 취급되기 때문에 두번째 인덱스 연산자는 비워두지 말아야합니다.

혹은 &로 인자를 넣어서 첫번째 배열의 첫번째 칸의 주소값을 가져올 수도 있습니다.

미로탐색

마이크로마우스

  • 문제 정의 : 1차 시도에서 탐색후, 2차 시도에서 최단 거리를 주행합니다.

  • 미로의 표현 : 2차원 배열로 표현합니다 (0 = 길 1 = 벽)

미로탐색 알고리즘

  • 우선법(right hand on wall) : 갈림길을 만났을 때, 우선적으로 오른족으로 갑니다.
while(still_in_maze){
    turn_right;
    while(wall_ahead){
        turn_left;
    }
    go_foward;
}

  • 최단경로 찾기 : 우선법 진행 과정의 좌표 리스트를 저장하고, 저장된 좌표 리스트의 중복되는 좌표 부분을 제거하여 최단 경로를 찾습니다.

  • 최단경로 찾기 방식 : k를 0으로 두고 미로의 좌표(k,i)과 (k,j)을 비교합니다. 같으면 사이 좌표 제거하고 아니면 j++합니다. 그리고 j가 마지막까지 도달하면 i++을 수행하고, k++하여 다시 처음으로 돌아갑니다.

Written on January 7, 2018