[알고리즘 랩스] rook (C++, 완전 탐색)

문제

체스에서 룩이라는 기물은 막혀있지만 않으면 룩의 위치에서 같은 행, 같은 열에 해당하는 칸 중 하나로 한 번 이동할 수 있다. 단, 특정 칸이 막혀있다면 그 칸에서부터 더 나아갈 수는 없다. 만약 룩이 아래 그림과 같이 5행 4열에 존재하고 같은 행열에 기물이 없다면 5행이나 4열에 존재하는 칸 중 어디로든 갈 수 있다. 예를 들어, 5행 2열 혹은 1행 4열로 움직일 수 있다. 차례에 주어진 이동 횟수는 한 번이므로 이동이 완료되었다면 상대방의 차례로 넘어간다.

체스는 킹만 잡히면 지게 되는 게임이다. 그 중에서도 알랩이는 룩으로 인해 게임을 지는 것을 극도로 싫어한다!

 

주어진 체스판의 상태에서 현재 차례가 상대의 차례일 때, 이번 차례에 알랩이의 킹이 상대방의 룩에게 잡힐 가능성이 있는지 알아보자.

 

입력

8줄에 걸쳐 8x8 체스판의 상태가 주어진다. 이때 0은 기물이 없는 상태이고, 1은 알랩이의 킹을 의미하고, 2는 상대의 룩을 의미하며 3은 그 외 다른 기물들을 의미한다. (킹은 하나만 존재하며, 상대의 룩은 최대 2개까지 있을 수 있다. 그 외 기물들은 최대 29개까지 있을 수 있다.)

 

출력

킹이 룩에게 잡힐 가능성이 있으면 1, 아니면 0을 출력한다.

 

 

---

#include <iostream>
#include <vector>

using namespace std;

typedef struct loc {
	int x;
	int y;
}loc;

int main() {

	vector< vector<int> > arr(8, vector<int>(8, 0));

	loc king;
	loc look;
	vector<loc> kimul;

	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			cin >> arr[i][j];

			if (arr[i][j] == 1) {
				king.x = i;
				king.y = j;
			}
			else if (arr[i][j] == 2) {
				look.x = i;
				look.y = j;
			}
			else if (arr[i][j] == 3) {
				loc tmp;
				tmp.x = i;
				tmp.y = j;
				kimul.push_back(tmp);
			}
		}
	}

	if (king.x == look.x) {

		int max, min;

		if (king.y > look.y){
			max = king.y;
			min = look.y;
		}
		else {
			max = look.y;
			min = king.y;
		}

		for (int i = 0; i < kimul.size(); i++) {

			if (kimul[i].x == king.x && (kimul[i].y > min && kimul[i].y < max)) {
				cout << 0 << endl;
				return 0;
			}
		}
	}
	else if (king.y == look.y) {

		int max, min;

		if (king.x > look.x) {
			max = king.x;
			min = look.x;
		}
		else {
			max = look.x;
			min = king.x;
		}

		for (int i = 0; i < kimul.size(); i++) {

			if (kimul[i].y == king.y && (kimul[i].x > min && kimul[i].x < max)) {
				cout << 0 << endl;
				return 0;
			}
		}
	}
	else {
		cout << 0 << endl;
		return 0;
	}

	cout << 1 << endl; 
	return 0;
} 

완전 탐색으로 해결할 수 있는 문제입니다. 격자판을 입력 받으면서 킹, 룩, 기물들의 좌표들을 저장합니다.

 

킹과 룩의 x 또는 y가 같다는 것은 우선 룩이 킹을 제압할 수 있는 가능성이 있습니다. 같지 않은 경우는 0을 출력합니다.

 

만약 같다면, 그 사이에 기물이 있는지 탐색하여 기물이 있다면 0, 없다면 탐색 반복문을 탈출하여 1을 출력합니다.