자료구조 프로그래밍 실습 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방향 이동에 대해 해결합니다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | // 방향정보 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; | cs |
2~4. 메인 알고리즘
1 2 3 4 5 6 7 8 9 10 11 12 | // 다돌았는지 체크하기 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; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | // 메인 알고리즘 // 시작점 처리하기 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; } | cs |
'Archived(CSE Programming) > 자료구조(C++)' 카테고리의 다른 글
자료구조 프로그래밍 Lab06) 이항 힙 만들기 (Binomial Heap) (0) | 2018.11.03 |
---|---|
자료구조 프로그래밍 Lab05) 최소 좌향 트리 만들기(Leftist Min Tree, Heap) (0) | 2018.11.03 |
자료구조 프로그래밍 Lab04) 그래프 모든 경로 찾기 C (두 vertex 사이) (0) | 2018.10.25 |
자료구조 프로그래밍 Lab03) 최소힙(Min Heap) 만들기! (2) | 2018.10.24 |
자료구조 프로그래밍_Lab02) 역대 최고가 주식 (0) | 2018.10.24 |