[Silver 1] 2615 오목

https://www.acmicpc.net/problem/2615

2615번: 오목

 

이 문제는 완전 탐색으로 오목을 구현하는 문제이다.

 

오목은 가로, 세로, 좌 대각, 우 대각으로 만들 수 있다.

또한 문제에서 오목이 만들어 졌을 때 가장 왼쪽의 인덱스를 출력해야한다.

 

문제의 특성을 생각해 봤을 때 한쪽 방향으로만 검사하면 된다는 것을 알 수 있다.

즉, 반드시 가장 왼쪽의 인덱스를 출력해야 한다는 것은 왼쪽으로만 검사하면 된다는 의미이다.

그러면 가로 검사, 대각 검사도 왼쪽으로만 검사하면 된다는 것이다.

세로은 위에서 아래로만 검사하면 된다.

 

오목만은 19x19 크기 이므로 4가지 방법에 대해서 완전 탐색하여도 시간 초과가 이루어지지 않는다.

 

문제에서 함정은 6목이 있을 수 있다는 것이다. 따라서 6목인지도 검사하여야한다.

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

int N;
int board[19][19];
int result = 0;
int resultX, resultY;

bool rowCheck(int y, int x) {
	int color = board[y][x];

	for (int i = 1; i <= 4; i++) {
		if (board[y][x + i] != color) return false;
	}

	if (board[y][x - 1] == color || board[y][x + 5] == color) {
		return false;
	}
	return true;
}
bool colCheck(int y, int x) {
	int color = board[y][x];

	for (int i = 1; i <= 4; i++) {
		if (board[y + i][x] != color)return false;
	}
	if (board[y - 1][x] == color || board[y + 5][x] == color) return false;

	return true;
}

bool diagonalCheck1(int y, int x) {
	int color = board[y][x];
	
	for (int i = 1; i <= 4; i++) {
		if (board[y+i][x+i] != color) return false;
	}
	if (board[y - 1][x - 1] == color || board[y + 5][x + 5] == color) return false;
	return true;
}

bool diagonalCheck2(int y, int x) {
	int color = board[y][x];

	for (int i = 1; i <= 4; i++) {
		if (board[y - i][x + i] != color) return false;
	}
	if (board[y + 1][x - 1] == color || board[y - 5][x + 5] == color) return false;
	return true;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	for (int i = 0; i < 19; i++) {
		for (int j = 0; j < 19; j++)
			cin >> board[i][j];
	}
	
	for (int i = 0; i < 19; i++) {
		for (int j = 0; j < 19; j++) {
			if (board[i][j] == 0)continue;

			if (rowCheck(i, j)) {
				result = board[i][j];
				resultY = i + 1;
				resultX = j + 1;
			}
			if (colCheck(i, j)) {
				result = board[i][j];
				resultY = i + 1;
				resultX = j + 1;
			}
			if (diagonalCheck1(i, j)) {
				result = board[i][j];
				resultY = i + 1;
				resultX = j + 1;
			}
			if (diagonalCheck2(i, j)) {
				result = board[i][j];
				resultY = i + 1;
				resultX = j + 1;
			}
		}
	}


	if (result != 0) {
		cout << result << '\n';
		cout << resultY  << ' ' << resultX << '\n';
	}
	else cout << result << '\n';

	
	return 0;
}