15612 체스판 위의 룩 배치

알고리즘 시간에 체스판 문제는 비숍 또는 퀸 문제인데 이 문제는 그보다 조금 쉬운 룩 문제이다. 처음에 문제를 제대로 읽지 않아 n-queen의 prunning 문제인줄 알았는데 알고보니 가로 세로에 같은 룩을 배치하면 안되는 문제이다.

문제에서 제시한 조건은 총 2가지이다.

- 룩은 정확히 8개의 룩이 있어야 한다. 

- 모든 룩은 서로 공격할 수 없어야 한다. 즉, 서로 다른 두 룩은 같은 열에 있거나 같은 행에 있으면 안 된다. 

 

때문에 1차원 백터 하나와 2차원 벡터(입력) 이 두개로 해결 가능하다.

#include<iostream>
#include<string>
#include<vector>

using namespace std;

int main(int argc, char** argv)
{
	int test_case;
	int T;
    
	cin>>T;
	
	for(test_case = 1; test_case <= T; ++test_case)
	{

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

		bool checkRow = false;
		bool checkCol = false;
		int rookCnt = 0;

		for(int i = 0; i < 8; i++)
		{
			string row;
			cin >> row;
			int count = 0;
			for(int j = 0; j < row.size(); j++)
			{
				arr[i][j] = row[j];
				if(row[j] == 'O')
				{
					if(v[j] >= 1)
					{
						checkCol = true;
						continue;
					}
					else
					{
						v[j]++;
					}
					count++;
					rookCnt++;
				}
			}
			if(count > 1)//가로 중복 확인
			{
				checkRow = true;
			}
		}

		if(!checkRow && !checkCol &&rookCnt==8)
		{
			cout << "#" << test_case << " yes\n";
		}
		else
		{
			cout << "#" << test_case << " no\n";
		}
	}
	return 0;
}