자료구조 프로그래밍_Lab01) 술 취한 바퀴벌레 문제

자료구조 프로그래밍 실습 1. 

술취한 바퀴벌레 문제.

문제 내용은 다음과 같습니다.

문제 

술취한 바퀴벌레는 M * N 의 이차원 배열을 헤매고 있습니다.

전체 배열을 전부 1번 이상 씩 방문할 때까지 

Random으로 8방향 중 한 방향으로 이동을 합니다.

단 시작점은 [m/2][n/2] 에서 시작합니다.

해결 - 알고리즘

문제 해결의 알고리즘은 다음과 같습니다.

0. 배열 초기화 (0~m+1, 0~n+1)

1. 방향 정리 (8방)

2. while( 다 방문할 때 까지)을 통한 반복문

3. 안에서 rand로 난수 받아서 다음방향 이동(단 , 0또는 m+1, 0또는 n+1 일때는 다시 난수받기)

4. 돌면서 방문하는 곳은 0에서 1로 체크

0.

배열 초기화는 사이즈 m+2 * n+2 의 배열을 할당합니다

그리고 후에 방문체크는 1~m, 1~n 부분에서만 합니다.

이렇게 큰 배열을 선언하는 이유는 복잡한 예외처리 과정을 생략하기 위해서입니다.

어떠한 난수를 받아서 방향을 가든 처리할 수 있도록 하기 위하여 

ex) 만약 배열을 m*n 사이즈로 선언하였을 경우 arr[0][0] 에서 위로 가는 방향의 난수가 나오면 

이를 다시 예외처리를 해야하는데 이를 고려하지 않기 위해서 m+2 * n+2 의 배열을 선언합니다

1.

다음 8방향 이동에 대해 해결합니다.

// 방향정보
typedef struct position {
    int row;
    int col;
}position;
 
// 8방 정보를 담을 배열
position dir[8];
 
// 8방초기화
dir[0].row = -1, dir[0].col = 0;
dir[1].row = -1, dir[1].col = 1;
dir[2].row = 0, dir[2].col = 1;
dir[3].row = 1, dir[3].col = 1;
dir[4].row = 1, dir[4].col = 0;
dir[5].row = 1, dir[5].col = -1;
dir[6].row = 0, dir[6].col = -1;
dir[7].row = -1, dir[7].col = -1;

2~4. 메인 알고리즘

// 다돌았는지 체크하기
int foundCheck(int m, int n) {
    // 반복문
    for (int i = 1; i<=m; i++)
        for (int j = 1; j <= n; j++) {
            if (mark[i][j] == 0)
                return -1; // 아직 덜 돈곳이 있다면 -1 반환
        }
 
    // 그 외에 다 돌았으면 1 반환
    return 1;
}

// 메인 알고리즘
 
// 시작점 처리하기
position now, next;
now.row = m / 2;
now.col = n / 2;
mark[now.row][now.col] = 1; //mark
 
while (1) {
 
    // 다 돌았으면 끝내기(foundCheck 함수는 방문하지 않은 곳을 검사하는 함수)
    if (foundCheck(m, n) == 1)
        break;
 
    // 다음 방향
    randDir = rand() % 8;
    next.row = now.row + dir[randDir].row;
    next.col = now.col + dir[randDir].col;
 
    // 갈수 없는 곳이라면
    if (next.row == 0 || next.row == m + 1 || next.col == 0 || next.col == n + 1) {
        continue;
    }
 
    // 다음 방향 이동
    now = next;
    maze[now.row][now.col]++; //횟수증가
    mark[now.row][now.col] = 1;
}