백준 1992번 쿼드트리

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;
}

나와 완벽히 같은 아이디어

내 알고리즘에 대한 확신을 가질 수 있었고, 다른 사람 코드를 읽는 연습도 할 수 있었다.

그리고 분할 정복이라 해서 다 분할 뒤 정복하는 것 뿐아니라
조건이 성립할 때까지 분할 후 성립하면 멈추는 것도 있다는 것을 알았다.