[C++] 백준 16955번 - 오목, 이길 수 있을까?

조금은 까다로웠던 구현 문제였다.

함수 이름을 BFS라고 써놨는데 그냥 check정도가 적당할 것 같다.

 

입력으로 X가 들어올때 vector에 집어 넣고, 이 vector 컨테이너 안에 있는 시작점들을 바탕으로 탐색을 시작하면 되는 문제였다.

오목이기 때문에 상하좌우 뿐만이 아니라 대각선으로도 이동할 수 있다는 것까지 고려해야 한다.

특이한점은 X가 5개로 연결되는 경우가 정답이 아니라 X가 4개 있고, 하나의 바둑돌을 놓을 수 있어야 정답이 된다.

#include <bits/stdc++.h>
#define endl '\n'
#define pii pair<int, int>
using namespace std;

const int m = 10;
char arr[m][m];
vector<pii> v;

const int dx[8] = { 1, 1, 1, 0, 0, -1, -1, -1 };
const int dy[8] = { 1, 0, -1, 1, -1, 1, 0, -1 };

bool bfs(int x, int y) {
	for (int i = 0; i < 8; i++) {
		int cnt = 1;
		int empty = 0;
		int nx = x, ny = y;
		for (int j = 0; j < 4; j++) {
			nx += dx[i];
			ny += dy[i];
			if (nx < 0 || ny < 0 || nx >= m || ny >= m) continue;

			if (arr[nx][ny] == 'X') cnt++;
			if (arr[nx][ny] == '.') empty++;
		}
		if (cnt == 4 && empty == 1) return true;
	}
	return false;
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	for (int i = 0; i < m; i++) {
		for (int j = 0; j < m; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 'X') v.push_back({ i, j });
		}
	}

	for (int i = 0; i < v.size(); i++) {
		int x = v[i].first, y = v[i].second;
		if (bfs(x, y)) {
			cout << 1 << endl;
			return 0;
		}
	}
	cout << 0 << endl;
	return 0;
}