[백준/BOJ] 2615번 오목 (C++)

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

2615번: 오목

그렇게 어렵지 않는 구현 문제였다. 주의할 점이 하나 있는데 오목인지 확인할 때, 다음과 같이 4방향으로 고려해야한다.

그림판으로 그려서 구리네요 죄송합니다.

4방향인데, 각각 2번씩 탐색을 하는 것이다. 이렇게 해서 오목이 되는지 확인하면 된다.

 

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

int map[20][20], win;
int dx[2][4] = {
	{-1, -1, -1, 0},
	{1, 1, 1, 0}
};
int dy[2][4] = {
	{-1, 0, 1, 1},
	{1, 0, -1, -1}
};
vector<pair<int, int> > res;
bool flag;

int cmp(pair<int, int> &a, pair<int, int> &b) {
	if(a.second == b.second) return a.first < b.first;
	return a.second < b.second;
}

void check(int x, int y, int k) {
	int pivot = map[x][y];
	queue<pair<int, int> > q;
	q.push({ x, y });
	
	int nx = x, ny = y;
	while(1) {
		if(nx + dx[0][k] < 0 || nx + dx[0][k] >= 19 || ny + dy[0][k] < 0 || ny + dy[0][k] >= 19) break; 
		if(map[nx + dx[0][k]][ny + dy[0][k]] == 0 || map[nx + dx[0][k]][ny + dy[0][k]] != pivot) break;
		nx += dx[0][k];
		ny += dy[0][k];
		q.push({ nx, ny });
	}

	nx = x, ny = y;
	while(1) {
		if(nx + dx[1][k] < 0 || nx + dx[1][k] >= 19 || ny + dy[1][k] < 0 || ny + dy[1][k] >= 19) break; 
		if(map[nx + dx[1][k]][ny + dy[1][k]] == 0 || map[nx + dx[1][k]][ny + dy[1][k]] != pivot) break;
		nx += dx[1][k];
		ny += dy[1][k];
		q.push({ nx, ny });
	}
	
	if(q.size() == 5) {
		if(pivot == 1) win = 1;
		else if(pivot == 2) win = 2;
		while(!q.empty()) {
			res.push_back(q.front());
			q.pop();
		}
		flag = true;
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	for(int i = 0; i < 19; i++) {
		for(int j = 0; j < 19; j++) {
			cin >> map[i][j];
		}
	}
	
	for(int i = 0; i < 19; i++) {
		for(int j = 0; j < 19; j++) {
			if(map[i][j] == 1 || map[i][j] == 2) {
				for(int k = 0; k < 4; k++) {
					check(i, j, k);
					if(flag) {
						sort(res.begin(), res.end(), cmp);
						cout << win << "\n";
						cout << res[0].first + 1 << " " << res[0].second + 1;
						return 0;
					}
				}
			}
		}
	}
	
	cout << win;
}