[알고리즘 트레이닝 북] 7번 체스판 문제

문제 설명

이번 문제는 체스판을 입력받아서 ‘체크메이트’ 상태를 판단해주는 프로그램이다. 체스판은 8 * 8개 격자로 이루어져 있고, 흰 말은 대문자 K(킹), R(룩), P(폰)… 등으로 입력받고 검은 말은 소문자로 입력받는다. 아무것도 없는 칸은 . 으로 표기하며, 체스판 모양 그대로 8개의 문자를 8개 행으로 입력받는다. 예를 들어

rnbqkbnr
pppppppp
........
........
........
........
PPPPPPPP
RNBQKBNR

이런 입력은 체스판 초기 셋팅 입력이 된다. 검은 말은 항상 위에서 시작하고 (따라서 검은 폰은 항상 아래쪽으로만 움직인다) 흰 말은 항상 아래에서 시작한다.
이런 입력을 받아서 검은색 킹이나 흰색 킹이 체크상태인지 확인해주는 프로그램을 만드는 것이 이번 문제의 목표이다.

풀어 보기

우선, 체스판은 앞의 5번 문제와 같이 각 모서리에 1줄의 여유를 두고, 10 * 10 배열에 입력받도록 하였다.

char a[10][10];
//2차원 배열로 입력받음
for (int i = 1; i < 9; i++)
	cin >> a[i];

이제 체크상태인지 검사를 하면 된다.

모든 말의 2차원 좌표(x, y)를 저장해 대수적으로 체크상태를 판별함
킹을 뺀 나머지 말들이 움직일 수 있는 위치에 다른 편의 킹이 있나 배열을 읽어가며 하나씩 검사
킹의 위치에서 말의 움직이는 특성에 따라 나눠서 잡아먹을 수 있는 위치에 해당 말이 있나 배열을 읽어가며 하나씩 검사 (2번과 반대로 말의 움직임을 역추적)

1번부터 생각을 하다 보니, 3번이 가장 편리한 방법인 것으로 생각되었다. 1번의 경우 변수를 너무 많이 필요로 하고, 2번의 경우는 모든 말에 대한 움직임을 읽어내야 하므로 체크 상태를 파악하는 데 필요치 않는 부분들이 프로그램에서 수행할 가능성이 많은 것 같았다. 그래서 생각된 것이 3번인데, 킹의 위치에서 ‘잡아먹을 수 있는’위치에 ‘잡아먹을 수 있는’ 말이 있는지만 판별하므로, 생각해볼 수 있는 가장 효율적인 방법이었다.
먼저, 킹의 위치는 프로그램상에서 계속 쓰여야 하므로 별도로 저장하였다.

//킹찾기
	for (int i = 1; i < 9; i++)
		for (int j = 1; j < 9; j++)
		{
			if (a[i][j] == (char)('k' - (iswhite * 32)))
			{
				k_x = j;
				k_y = i;
				break;
			}
		}

문제에서 흰 말과 검은 말을 대문자, 소문자로 구분하는 데, ASCII 코드 상에서 소문자가 대문자보다 32가 큰 코드를 갖고 있다. 따라서, 흰 말을 나타내는 문자는 대응되는 검은 말을 나타내는 문자에서 32를 빼주어야 한다. iswhite 는 현재 어떤 킹에 대한 체크를 검사하는지를 나타내는 bool 형 변수이다. (흰 색이면 TRUE)
이 iswhite 변수는 킹을 먹을 수 있는 말, 즉 체크 상태인지 검사를 할 대상이 소문자인지, 대문자인지를 판별할 뿐만 아니라, 폰의 경우에는 말의 움직임 자체가 말의 색깔에 따라 달라지므로, 이 때에도 사용되었다. 좀 헛갈릴 수 있는데, iswhite 는 잡아 먹힐(…) 킹의 색깔을 나타내는 것이다. 따라서 잡아 먹을 말의 색깔과 반대의 색을 나타낸다.

bool checkp(const char(*a)[10], int k_x, int k_y, bool iswhite)
{
	return (a[k_y - 1 + iswhite * 2][k_x - 1] == (char)((int)'P' + (iswhite * 32))
		|| a[k_y - 1 + iswhite * 2][k_x + 1] == (char)((int)'P' + (iswhite * 32)));
	//킹의 윈쪽 아래(킹이 흰색이면 위)에 폰이 있는 경우 or
	//킹의 오른쪽 아래(킹이 흰색이면 위)에 폰이 있는 경우 TRUE 반환
}

이렇게 잡아 먹을 수 있는 말의 종류별로 bool 함수를 만들었다.

bool checkcross(const char(*a)[10], int k_x, int k_y, bool iswhite, char chkwhat)
{//상하좌우에 chkwhat이 있나 검사, 빈 칸은 무시, chkwhat은 체크 할 말의 대문자
	for (int i = 1; k_x + i < 9; i++)
	{// 킹 오른쪽 chkwhat 있는지 검사
		if (a[k_y][k_x + i] == '.')
			continue;
		else if (a[k_y][k_x + i] == (char)((int)chkwhat + (iswhite) * 32))
			return 1;
	}

	for (...){...} // 오른쪽
	for (...){...} // 위
	for (...){...} // 아래
}

chkwhat 에 'R' 을 넣으면 룩에 대한 체크를 검사하는 함수가 된다. 이를 따로 변수로 둔 것은 퀸은 룩+비숍의 움직임을 갖기 때문에 퀸에 대한 체크를 검사할 때 재탕(!)하기 위함이다.

bool checkq(const char(*a)[10], int k_x, int k_y, bool iswhite)
{
	return (checkcross(a, k_x, k_y, iswhite, 'Q') || checkdiag(a, k_x, k_y, iswhite, 'Q'));
}

checkdiag 함수는 앞의 함수와 같이 대각선상의 말에 대한 체크를 검사하는 함수이다. checkcross 에서 배열 안의 +1 또는 -1을 약간만 변형하면 만들어진다. 여기에도 chkwhat 변수가 인자로 들어가 퀸에 대한 체크를 검사할 때 이렇듯 훌륭하게(…) 재탕할 수 있었다.
이렇게 모든 말의 종류(또는 움직임의 특성)에 대한 체크 함수를 다 만들면, 여기에서 반환되는 bool 값을 그냥 OR 로 합하기만 하면 체크인지 아닌지 알 수 있다.

bool checkmate(const char(*a)[10], bool iswhite)
{
	return (checkq(a, k_x, k_y, iswhite) || checkp(a, k_x, k_y, iswhite)
	|| checkcross(a, k_x, k_y, iswhite, 'R') || checkdiag(a, k_x, k_y, iswhite, 'B')
	|| checkn(a, k_x, k_y, iswhite));
		//퀸, 폰, 룩, 비숍, 나이트 순서대로 검사
}

이 리턴값이 체크인지 iswhite 에 해당되는 색의 킹이 체크 상태인지 아닌지를 나타낸다. 위에서 검사 순서를 체스를 잘 알면 ‘잡아먹을 가능성이 큰’ 순서대로 바꿨을 테지만 체스를 잘 모르므로 그냥 아무렇게나 짰다. 한 가지 고려했던 것은 저렇게 OR를 연속적으로 썼을 때, 앞에서부터 하나씩 함수를 수행하다가 TRUE값이 한번이라도 나오면 (체크상태인 것이 발견이 되는 즉시) 다음 함수를 수행하지 않고 TRUE를 반환해준다는 것이다. (MSDN: ||연산자) 참고로 AND연산에서도 FALSE가 한 번이라도 나오면, 다음 것을 고려하지 않고 바로 FALSE를 반환한다고 한다.
실제로 구현한 것은 여기에 몇 가지를 추가했지만 (킹이 없는 체스판 입력 인식… 킹 위치 찾는 것을 포함… 등등) 가장 주요한 프로그램 논리를 대부분 설명한 것 같다.

퍽 재미있지만 흑과 백의 말을 프로그램에게 어떻게 구분시켜 알려줄 것인지, 말의 움직임을 어떤 방식으로 역추적할 것인지… 등등 구현하는 데 꽤 전체 코드는 github 에서 확인할 수 있다.
책에 나온 대로 실행해본 결과 잘 작동하는 모습을 볼 수 있었다.
quiz7_picture