| 달팽이 배열 |
그림을 보면 이해할 수 있을 것이라 생각합니다. N,M을 입력받고 N x M의 행렬에 숫자들을 그림처럼 나선형으로 채워넣는 문제입니다. 일명 달팽이배열이라고도 불리며, 알고리즘 테스트 문제로도 자주 활용되는 것으로 알고 있습니다.
이전에 한번 접한적이 있는데 새롭게 풀려고 하니 생각보다 헤매서 정리할겸 포스트를 작성합니다.
접근
접근단계에서, 문제를 단순화 시켜서 생각하는 작업이 필요합니다.
위의 문제를 start포인트부터 말을 나선형으로 이동하여, 모든 0을 찾아서 잡아먹는 게임이라고 생각했더니 한결 접근하기가 편해졌습니다. 따라서 N x M의 행렬에서 0이 모두 사라진다면 반복은 끝나게되는 것임을 알 수 있습니다.
이제 다음으로 구체적인 알고리즘을 구현하기위해 나선형으로 이동하는 것이 어떤 패턴인지 생각해봅니다.
오른쪽으로 가다가 막히면 아래로 가고, 아래로 가다가 막히면 왼쪽으로 또 위로 이 작업이 반복되고 있습니다.
방향만을 서술해보면
앞의 네가지 패턴이 반복된다는 것을 확인할 수 있습니다.
위의 내용을 종합하면
모든 0이 사라질때까지 나선형으로 이동하는 패턴을 반복하게 해주면 됩니다.
풀이
패턴에 대한 구체적인 알고리즘을 생각해보겠습니다.
먼저 right는 오른쪽으로 이동하는 알고리즘을 말합니다. 4 x 4 행렬에서 처음 start포인트를 생각하면, 3번 오른쪽으로 말을 이동해야합니다. 그 결과는 다음과 같을 것입니다.
이 부분을 코드로 구현하게 되면, i가 행 j가 열을 가리키는 배열arr에서 다음과 같이 구현가능합니다.
그리고 다음은 down 즉 밑으로 이동하는 알고리즘입니다.
아래로 이동하면서 숫자를 채워줍니다. 같은방식으로 left와 up을 작성할수있고
이것을 처음 생각했던 모든 0이 없어질때까지, 즉 숫자 a가 N x M이 될때까지 반복해주면 됩니다.
구현 코드
|
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
#pragma warning(disable:4996)
#include <stdio.h>
int arr[100][100];
int main() {
int N,M;
scanf("%d %d", &N,&M);
int i = 0, j = 0,a=1;
//0으로 초기화해서 게임판 만들기
for (i = 0; i < N; i++) {
for (j = 0; j <M; j++) {
arr[i][j] = 0;
}
}
//start포인트 설정
i = 0;
j = 0;
arr[i][j] = 1;
a = 2;
//0 잡아먹기 게임시작
while (a<=N*M) {
while (j+1<M && arr[i][j + 1] == 0) {
j++;
arr[i][j] = a;
a++;
}
while (i+1< N&&arr[i + 1][j] == 0) {
i++;
arr[i][j] = a;
a++;
}
while (j-1>=0&&arr[i][j - 1] == 0) {
j--;
arr[i][j] = a;
a++;
}
while (i-1>=0&&arr[i - 1][j] == 0) {
i--;
arr[i][j] = a;
a++;
}
}
for (i = 0; i <N; i++) {
for (j = 0; j <M; j++) {
printf(" %d", arr[i][j]);
}
printf("\n");
}
}
|
cs |
'지난 학기들의 기록 > 자료구조' 카테고리의 다른 글
| [자료구조] 배열에 대각선으로 숫자 채우기 (0) | 2021.03.22 |
|---|
댓글