본문 바로가기
Windows Developer/자료구조

[자료구조] 배열과 미로 탐색

빡썽 2010. 8. 2. 02:42

4.1 배열의 정의

  • 배열의 정의
  • 1차원 배열 사용법

 

C++ 배열 정의

  • 연속된 메모리 공간을 차지하는 같은 타입의 데이타 집합
  • 정적인 데이타 타입으로 그 크기가 미리 정해져 있음 ( 정적이라는 것은 바뀌지 않는다는 의미 )
  • 배열의 인덱스 사용은 사용자의 책임

    . 인덱스는 0 ~ 크기 -1 까지

    . 배열 자체에 크기 정보는 없다 ( a[ 10 ]을 사용하여도 컴파일 에러는 발생하지 않으나 실행시에 Memory error가 난다. )

  • 데이타형 배열명[ 배열의 크기 ];

int array[ 10 ];        // index는 array[ 0 ] ~ array[ 9 ]

int array2[ 5 ] = { 1, 2, 3, 4, 5 };    // 정의와 동시에 초기화

| | | | 1 | 2 | 3 | 4 | 5 | | | | | |    // 총 4 * 5 = 20byte

array2가 가리키는 곳

 

배열과 포인터의 관계

  • 배열의 이름은 배열이 저장된 메모리의 선두를 가리키는 상수( constant ) 포인터이다.
  • sizeof( array ) == 20, sizeof( parray ) == 4
  • 인덱스 연산자( [] )는 array[ n ]은 *( array + n )과 같은 의미

int array[ 5 ] = { 1, 2, 3, 4, 5 };

 

array = array + 1;    // error! 배열이름은 상수포인터로 변경 불가

int v1 = array[3];

int v2 = *( array + 3 );    // 4번째 값

 

int* parray = array;    // 선두를 가리키는 포인터가 대입됨

parray = parray + 1;    // 2번째로 전진 가능

v1 = parray[ 3 ];    // 배열의 4번째 값

v2 = *( parray + 3 );

 

함수에서 1차원 배열 사용

  • C++의 배열은 크기 정보가 없다

    배열의 끝에 특정값을 넣는 방법

    . C++의 스트링 : 끝에 NULL 값 ( char* str 스트링의 크기를 알고자 할때 )

  • 배열의 크기를 따로 지정하는 방법

int average( int a[ ], int n )    // 혹은 int average( int* a, int n )

{

    int sum = 0;

    for( int i = 0; i < n; i ++ )

        sum += a[ i ];

    return ( sum / n );

}

 

void main( void )

{

    int Array[ 5 ] = { 1, 2, 3, 4, 5 };

    int average = average( Array, 5 );

}

4.2 다차원배열

  • 다차원 배열의 구조
  • 다차원 배열의 사용법

 

다차원 배열의 정의

  • 다차원 배열의 정의

    인덱스 연산자를 차원수 만큼 쓴다

  • Array[ 3 ][ 3 ]에서

    Array[ 0 ], Array[ 1 ], Array[ 2 ]는 각각 세개짜리 정수 배열을 가리킴.

    sizeof( Array[ 0 ] ) == 12, sizeof( Array[ 0 ][ 0 ] ) == 4

int Array[ 3 ][ 3 ] =    // 다차원 배열의 초기화

{

    { 1, 2, 3 },    // Array start pointer

    { 4, 5, 6 },    // Array + 1이 가리키는 곳

    { 7, 8, 9 }    // Array + 2이 가리키는 곳

};

혹은 이렇게 써도 상관은 없는데 보기가 좀..

int Array[ 3 ][ 3 ] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

 

함수에서 다차원 배열 사용

int average( int m[ ][ 3 ] )

{    // int average( int* (m[3]), int n )과 동일

    int nSum = 0;

    for( int i = 0; i < 3; i ++ )

        for( int j = 0; j < 3; j++ )

            nSum += m[ i ][ j ];

    return nSum / ( 3 * 3 );

}

 

int nArray[ 3 ][ 3 ];

int average = average( nArray );

 

int average( int* m, int n1, int n2 )    // int형의 일차원 배열이라고 봄

{

    int nSum = 0;

    for( int i = 0; i < n1; i++ )

        for( int j = 0; j < n2; j++ )

            nSum += m[ i * n1 + j ];    // n1은 { }, { }, { }, ...

    return nSum / ( n1 * n2 );

}

 

int nArray[ 3 ][ 3 ];

int average = average( &nArray[ 0 ][ 0 ], 3, 3 );

 

int tri[ 3 ][ 4 ] [ 2 ];

int func( int t[ ][ 4 ][ 2 ] )

{

    // ...

}

 

result = func( tri );

 

int tri[ 3 ][ 4 ][ 2 ];

int func( int* m, int n1, int n2, int n3 )

{

    // ...

    sum += m[ i * n2 * n3 + j * n3 + k ];    // 3중 for문( i, j, k )

}

 

r = func( tri[ 0 ][ 0 ][ 0 ], 3, 4, 2 );


 

4.3 미로의 표현과 그리기

Robot Project ( 미로 탐색 프로그램 )

  • 미로 문제의 정의
  • 미로의 표현법
  • 미로 그리기

 

문제의 정의 ( 알고리즘에서 가장 중요한 '내가 지금 해결하고자 하는 문제가 무엇인가?' )

  • 마이크로 마우스 ( 바퀴가 달려있고 머리쪽에 벽이 있는지 여부를 판단하는 샌서가 있다. )

    자체 구동 능력과 자체 판단 능력을 가지고 있는 미로 탐색 로봇

    1차 시도에서 탐색 후, 2차 시도에서 최단거리 운행


      미로 그리기




















조금 깔끔하게 그리는 방법을 찾아보자.

0 1 0

0 1 1

0 1 0

가운데를 기준으로 상하좌우를 판단하여 그림을 그린다.

 

방향을 나타내는 상수

UP, RIGHT, DOWN, LEFT를 정의한다.

1, 2, 4, 8로 정의하는 이유는 20, 21, 22, 23을 나타내는데 4Bit 단위로 나타냈을때, | 1 | 0 | 0 | 1 |이라면 UP, LEFT이다.

0001 이면 UP

0002 이면 RIGHT

0003 이면 UP | RIGHT

0004 이면 DOWN

...

1111 이면 UP | RIGHT | DOWN | LEFT가 된다.

 

미로 그리기 함수들

  • CMaze::GetShape

    주위의 벽배치에 따라 벽 모양 코드를 리턴함

  • CMaze::DrawMaze

    GetShape을 이용하여 실제로 미로를 그림

int CMaze::GetShape( int x, int y )

{

    int shape = 0;        // 벽 모양 번호

    if( m_arrayMaze[ y ][ x ] != 0 )    // 벽이 있는 경우에만 경우의 수를 따진다. 0은 길

    {

        if( y > 0 && m_arrayMaze[ y-1 ][ x ] )    // 위쪽에 벽이 있나? y > 0은 범위 지정

            shape |= UP;    // or 연산을 하여 합친다.

        if( y < MAZE_SIZE - 1 && m_arrayMaze[ y+1 ][ x ] )

            shape |= DOWN;

        if( x > 0 && m_arrayMaze[ y ][ x-1 ] )

            shape |= LEFT;

        if( x < MAZE_SIZE - 1 && m_arrayMaze[ y ][ x + 1 ] )

            shape |= RIGHT;

    }

 

    return shape;

}

 

미로를 그려주는 부분

( i, j ) * 16 pixel씩 띄어서 16 x 16의 픽셀을 dcMem에 그리는데 shape번호*16을 가져와서 SRCCOPY한다.

for( int j = 0; j < MAZE_SIZE; j++ )

{

    for( int i = 0; i < MAZE_SIZE; i++ )

    {

        int shape = GetShape( i, j );

        pdc->Bitblt( i*16, j*16, 16, 16, &dcMem, shape*16, 0, SRCCOPY );

    }

}

 

4.4 미로탐색 알고리즘

  • 탐색 알고리즘 : 우선법
  • 우선법의 구현

 

우선법 ( Right Hand On Wall )

  • 갈림길을 만났을때 우선적으로 오른쪽으로 간다
  • 오른손을 벽에 대고 가기

어떻게 알고리즘 적으로 표현할 것인가?

while( Still_in_Maze )    // 아직 미로 안에 있다면 ( 끝나는 조건 )

{

    Turn_Right;    // 오른쪽 방향으로 돈다

    while( Wall_Ahead )    // 내 눈 앞에 벽이 있는가?

    {

        Turn_Left;    // 있으면 왼쪽으로 돈다

    }

    Go_Forward;    // 없으면 앞으로 전진한다.

}

직접 그림으로 그려보고 테스트 해보자.

 

함수로 어떻게 표현할까?

기본 함수들1

bool CMaze::StillInMaze( int x, int y )

{

    if( x > 0 && x < MAZE_SIZE - 1 && y > 0 && y < MAZE_SIZE - 1 )

        return true;

    else

        return false;

}

 

bool CMaze::WallAhead( int x, int y, int dir )

{

    x = ( dir == LEFT ? --x : dir == RIGHT ? ++x : x );

    y = ( dir == UP ? --y : dir == DOWN ? ++y : y );

    return m_arrayMaze[ y ][ x ] != 0;

}

 

void CMaze::GoForward( int& x, int& y, int dir )

{

    x = ( dir == LEFT --x : dir == RIGHT ? ++x : x );

    y = ( dir == UP ? --y : dir == DOWN ? ++y : y );

}

 

void CMaze::TurnLeft( int &dir )

{

    dir >>= 1;

    dir = ( dir == 0 ? LEFT : dir );

}

 

UP = 1

LEFT = 8    RIGHT = 2

    DOWN = 4

 

TurnLeft

LEFT >> DOWN >> RIGHT >> UP , UP을 >> 연산 하면 0이 되기 때문에 0 일경우 LEFT로 간다. ( 쉬프트 연산 사용시 )

 

void CMaze::TurnRight( int &dir )

{

    dir <<= 1;

    dir = ( dir > LEFT ? UP : dir );

}

 

void CMaze::RightHandOnWall( int x, int y, int dir )

{

    while( StillInMaze( x, y ) )

    {

        TurnRight( dir );

 

        while( WallAhead( x, y, dir ) )

        {

            TurnLeft( dir );

        }

 

        GoForward( x, y, dir );

    }

}

 

4.5 최단경로 찾기

  • 경로의 저장
  • 최단경로 구하기

 

최단경로 찾기 방법

  • 우선법 진행 과정의 좌표 리스트를 배열에 저장
  • 저장된 좌표리스트에서 중복되는 좌표부분 잘라냄

    • 들어갔다가 돌아 나오는 부분이 중복 된다. ( 2, 5 ) 이 부분을 잘라주자.

    배열 메모리

    || x | y | x | y | . . . . . . | -1 | -1 ||

     

    void CMaze::ShortestPath()

    {

        int i, j = 0;

        int x, y;

        int x1, y1;

        

        while( m_arrayRecord[ i ] >= 0 )    // 끝부분에 -1이 저장되어 있으므로 이동경로만큼 첫번째 좌표 비교 주르륵, 두번째 좌표 비교 주르륵 이런식.. ( 2, 5 )에서 걸리게 된다.

        {

            x = m_arrayRecord[ i ];    // 배열에 저장되어 있는 좌표값을 얻어온다.

            y = m_arrayRecord[ i + 1 ];

            j = i + 2;    // j는 비교할 좌표 ( 한 좌표가 두개의 정수이므로 다음 좌표는 +2이다. )

     

            while( m_arrayRecord[ j ] >= 0 )

            {

                x1 = m_arrayRecord[ j ];    // 배열에 저장되어 있는 값을 가져와서

                y1 = m_arrayRecord[ j + 1 ];

                if( x == x1 && y == y1 )    // 비교한다.

                    j = DeletePath( i, j );    // 같으면 그 좌표값을 지운다.

                j += 2;

            }

            i += 2;

        }

    }

     

    4. 결론

    • 배열은 연속된 메모리 공간을 차지하는 같은 타입의 데이타 집합 이다.

      . 배열 자체는 크기 정보가 없다.

      . 포인터와 배열의 차이점 ( a[ n ] == * ( a + n ); )

    • 미로탐색

      . 미로를 그리기 위한 코드 체계 ( 쉬프트 연산의 활용 )

      . Right Hand On Wall

      . 최단경로를 구하기 위한 중복 제거

      [출처] Chapter 4. 자료구조 1 - 배열과 미로 탐색|작성자 천상의빛




티스토리툴바