https://www.acmicpc.net/problem/1992
내 알고리즘
내 코드
#include <stdio.h>
char array[64][65];
void QuadTree(int left, int right, int high, int low)
{
int mid_column = (left + right) / 2;//가로 절반
int mid_row = (high + low) / 2;//세로 절반
int first = array[high][left];
int i, j;
for (i = high; i <= low; i++)//i와 j가 각각 low보다 1 right보다 1커져서 탈출할 가능성이 있다.
{
for (j = left; j <= right; j++)
{
if (first != array[i][j])
{
break;
}
}
if (first != array[i][j] && j<= right)//j<=right는 break에 걸렸다는 중요한 증거
{
break;
}
}
//i, j는 반복문을 다 돌고 탈출하면 최대보다 1 더 크므로 break에 걸린 것과 구별된다.
if (i<= low && j <= right)//low가 가장 낮은 곳의 좌표였느넫, 이거 햇갈리네, 이거 때문에 하.... 앞으로는 가장 큰 수를 high, 가장 작은 수를 low라 하자 그냥
{
printf("(");
QuadTree(left, mid_column, high, mid_row);
QuadTree(mid_column + 1, right, high, mid_row);
QuadTree(left, mid_column, mid_row + 1, low);
QuadTree(mid_column + 1, right, mid_row + 1, low);
printf(")");
return;
}
else
{
printf("%d", first - 48);
}
return;
}
int main()
{
int N, i, j;
scanf("%d", &N);
for (i = 0; i < N; i++)
{
scanf("%s", array[i]);
}
QuadTree(0, N - 1, 0, N - 1);
return 0;
}
이 코드를 작성하면서 배운 것 ->
1. low와 high는 햇갈리지 않게 위치보다 값을 기준으로 변수 이름을 정해야겠다.
2. 반복문을 다 돈 것과 break의 구별은 i,j값을 통해 확인할 수 있다.
3. 재귀함수의 디버깅은 매개변수를 통해 하면 효과적 (printf를 적극 활용하자)
다른 사람 코드
maniadb님의 코드
https://www.acmicpc.net/user/maniadb
나보다 메모리를 적게 먹었길래 찾아보았는데 7년전이라서 같은 알고리즘이라도 메모리를 적게 먹은건가 싶기도 하다.
#include <stdio.h>
char matrix[64][64];
void quadTree(int i_start, int j_start, int n)
{
int i, j, res;//res가 뭘까?
if (matrix[i_start][j_start] == '0') res = 0;
else res = 1;
for (i = i_start; i < i_start + n; i++)//n은 가로세로 길이
{
for (j = j_start; j < j_start; j++)
{
if (res == 0 && matrix[i][j] == '1')//첫숫자가 0이고 검사범위 중 하나라도 1 이면
{
res = -1;
break;
}
else if (res == 1 && matrix[i][j] == '0')
{
res == -1;//res가 -1 이란건 검사 범위내에 다른 숫자가 있다는 것
break;
}
}
}
if (res == 1) printf("1");
else if (res == 0) printf("0");
else
{
printf("(");
quadTree(i_start, j_start, n / 2);
quadTree(i_start, j_start + n / 2, n / 2);
quadTree(i_start + n / 2, j_start, n / 2);
quadTree(i_start + n / 2, j_start + n / 2, n / 2);
printf(")");
}
return;
}
int main()
{
int i, j, n;
scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%s", matrix + i);
}
quadTree(0, 0, n);
printf("\n");
return 0;
}
나와 완벽히 같은 아이디어
내 알고리즘에 대한 확신을 가질 수 있었고, 다른 사람 코드를 읽는 연습도 할 수 있었다.
그리고 분할 정복이라 해서 다 분할 뒤 정복하는 것 뿐아니라
조건이 성립할 때까지 분할 후 성립하면 멈추는 것도 있다는 것을 알았다.