[알고리즘 트레이닝 북] 5번 그래픽 편집기 문제

문제 설명

간단한 대화형 그래픽 편집기 흉내를 낼 수 있는 프로그램을 작성하는 문제이다. 이내의 MxN크기의 직사각형 배경에, 색깔은 영어 대문자로 표기한다. 왼쪽 구석을 (1, 1)로 하고, 오른쪽으로 가면 열 번호가, 아래로 가면 행 번호가 증가한다.
명령은 한 줄 단위로 이루어지며 한 명령안에서 각 요소는 공백으로 구분된다. 예를 들어, L X Y C 는 (X, Y)픽셀을 ‘C’라는 색으로 칠하라는 L이라는 형태의 명령이다. 문제의 가장 핵심이 되는 부분은 F명령인데, F X Y C라고 입력되면 (X, Y)픽셀과 색이 같으면서 상하좌우에 인접한 픽셀들을 칠하는 것으로, 개념적으로 그림판의 ‘페인트 통’ 도구와 같은 역할이다.

구현해야 할 명령들
I M N (MxN 이미지 생성 후 ‘O’로 칠하기)
C (이미지 전체를 ‘O’로 칠하기)
L X Y C (X,Y 픽셀을 ‘C’로 칠하기)
V X Y1 Y2 C (X열 중 Y1행~Y2행에 해당하는 부분 ‘C’로 칠하기)
H X1 X2 Y C (Y행 중 X1열~X2열에 해당하는 부분 ‘C’로 칠하기)
K X1 Y1 X2 Y2 C (X1-X2, Y1-Y2에 해당하는 직사각형 부분 ‘C’로 칠하기)
F X Y C (페인트 통 도구, ‘C’로 칠하기)
S Name (Name출력 후, 이미지 내용 출력하기)
X (세션 종료)

풀어 보기

M, N이 250이내의 수라는 문제의 조건에 따라 250*250크기의 2차원 char 배열을 만들어 배열의 각 요소에 영어 대문자로 표기된 색깔 정보를 담게 하였다.

const int SIZE = 252;
char arr[SIZE][SIZE];
arrInit(arr);

void arrInit(char (*arr)[SIZE])
{
	for (int i = 0; i < SIZE; i++)
		for (int j = 0; j < SIZE; j++)
			arr[i][j] = NULL;
}

2개의 여유를 둔 것은 명령을 구현할 때, 상하좌우에 값이 NULL인 요소를 주어 반복문에서 반복 조건을 줄 때나 이미지의 끝임을 알아차리기 쉽게 하기 위함이다. 3번 문제에서도 이렇게 2차원 배열을 그래픽 요소 등으로 사용할 때 네 모서리에 1줄의 여유를 주면 편리하게 사용할 수 있었다.
arrInit은 배열의 모든 요소를 NULL로 셋팅한다. 이중 반복문을 활용했다. 여기에서 arr의 자료형을 살펴 볼 필요가 있다. arr은 2차원 배열이다. 처음에는 arr이 더블 포인터의 자료형과 호환될 줄 알고 char** ptr = arr 와 같은 형태가 가능한 줄 알았는데, 아니었다. arr은 더블포인터가 아닌, 252개 요소를 가진 배열에 대한 포인터이다. 즉, 이 문제의 개념으로 보았을 때 첫 행에 대한 포인터이다. 코드로 쓰면 &arr[0]과 같은 의미를 지닌다고 볼 수 있다. 따라서, char arr[252][252]에 해당하는 포인터(등가포인터라고 하더라)는 char (*ptr)[252]와 같은 형태이다. 이런 형태를 배열포인터라고 한다. 즉 arr의 자료형은 char (*)[252]와 같은 형태이다. 이 둘은 자료형까지 완전히 같은 것이기 때문에 ptr[i][j] = arr[i][j] 이며, 배열처럼 호출이 가능하다. 참고로, 이중 포인터는 1차원 포인터배열의 등가포인터다. 즉, char ** ptr = *arr[i] 처럼 쓸 수 있다.

각 명령들을 하나씩 별도의 함수로 구현하였다. I, C, L, V, H, K의 구현은 어렵지 않았다.

void kFunc(int x1, int x2, int y1, int y2, char c, char(*arr)[SIZE])
// x1~x2, y1~y2 직사각형 c로 칠하기
{
	for (int i = x1; i <= x2; i++)
		for (int j = y1; j <= y2; j++)
			arr[j][i] = c;
}

나머지 코드는 github 에서 볼 수 있다. 문제의 핵심은 F명령이었다. 이미지 편집 프로그램에서 종종 사용하는 ‘페인트 통’ 도구와 같은 것이다. 입력된 X, Y픽셀과 같은 색으로 이루어진 ‘붙어 있는’ 부분을 모두 ‘C’라는 색으로 칠한다. 어떻게 구현해야 할까?

X, Y 픽셀과 같은색인 부분을 선택 한 후 X, Y와 붙은 부분을 판단한다?
X, Y 픽셀 상하좌우 4개 픽셀을 검사해 찾아 칠하고 또 칠한 부분의 상하좌우를 검사해 칠하고 … (반복)
H, V 명령을 활용해 X, Y가 포함된 같은 색 ‘선’을 찾고, 이를 다시 H, V 명령을 통해 ‘선’을 확장해가면서 색칠한다?
등등…

다양한 방법이 있을 수 있지만, 1번은 같은 색인지 구분하는 것 까지는 쉬운데, 붙었냐 안붙었냐를 판별하는 것이 복잡할 것 같아 2번을 반복문을 사용하여 구현하는 것을 생각해 보았는데, 쉽지 않았다. 그래서 3번을 생각했는데, Y행에서 같은 색인 부분 (ex. X = 3~8, Y = 12)을 선 형태로 찾고, 그 다음 X의 범위에서 열 단위로 스캔(?)하는 방법을 생각해 보았는데… 만약 이미지가 직사각형이나 원형 등이 아니라 오목, 볼록한 부분이 있으면 해당 부분을 색칠하지 못하는 문제가 있었다. 그래서, 다시 2번으로 돌아 왔는데, 반복이 아닌 재귀를 통하면 더 단순한 형태로 해결하는 방법이 있을 것 같았다.

void fFunc(int x, int y, char c, char(*arr)[SIZE]) // x, y기준으로 c로 색 채우기
{
	char bc = arr[y][x]; // (x, y)의 색깔 bc에 저장
	arr[y][x] = c;
	fill(x, y, bc, c, arr);
}

void fill(int x, int y, char bc, char c, char(*arr)[SIZE])
// x, y 기준으로 시계방향(위-오른-아래-왼)으로 돌면서 color를 호출시킨다
{
	int tempX = x, tempY = y - 1; // 한 칸 위 픽셀
	color(tempX, tempY, bc, c, arr);

	tempX = x + 1, tempY = y; // 한 칸 오른쪽 픽셀
	color(tempX, tempY, bc, c, arr);

	tempX = x, tempY = y + 1; // 한 칸 아래 픽셀
	color(tempX, tempY, bc, c, arr);

	tempX = x - 1, tempY = y; // 한 칸 왼쪽 픽셀
	color(tempX, tempY, bc, c, arr);
}

void color(int tempX, int tempY, char bc, char c, char(*arr)[SIZE])
// tempX, tempY가 bc와 같은색이면 c로 칠하고, fill을 호출해 tempX, tempY를 기준으로 다시 시계방향으로 돌린다(재귀)
{
	if (arr[tempY][tempX] == bc) // bc와 현재 픽셀이 같은색인지 검사
	{
		arr[tempY][tempX] = c; // 같으면 c로 색 바꾸고
		fill(tempX, tempY, bc, c, arr); // 현재 픽셀을 기준으로 fill 호출해 시계방향으로 다시 돌리기
	}
}

fill은 (x, y)를 기준으로 위, 오른쪽, 아래, 왼쪽 픽셀 순서로 color에 좌표를 넘겨 주어 호출한다. color는 해당 픽셀이 원래의 (x, y)의 색과 똑같으면 ‘C’로 칠하고 다시 fill 을 호출해 그 픽셀을 기준으로 다시 시계방향으로 인접한 픽셀에 대해 색깔 검사를 하게 된다. 이렇게 재귀 함수를 만들 때에는 문제 전체에 주목하기보다 쪼개어 본 작은 과정과 그 다음 과정이 ‘똑같은 형태’ 인 것을 발견하는 것이 중요한 것 같다. 여기에서는 만약 x, y에 인접한 어떤 픽셀이 x, y와 같은 색이라면, 그 픽셀을 기준으로 또다시 인접한 어떤 픽셀을 찾는 과정이 재귀적이다.

여기까지 해결했으면, 이제 입력을 줄 단위로 처리할 루프문 안에 명령에 따라 해당하는 함수를 호출하는 선택기만 만들면 된다.

while (order != 'X')
	{ // 명령 선택기
		cin >> order;

		if (order == 'I')
		{...}
	...
	}

이런 형태로 구현하였다. 이렇게 하면 지정된 명령 외의 명령이 들어오면 해당 명령을 무시하고 새로운 명령을 기다리게 된다. 전체 코드는 github 에서 볼 수 있다.

책에 나온 대로 실행해본 결과 잘 작동하는 모습을 볼 수 있었다.
quiz5_picture