[C++] 백준 2615번: 오목

문제 링크

2615번: 오목

문제 요약

오목판이 주어지면 누가 이겼는지 출력해야 한다. 비기는 경우는 주어지지 않으며, 승패가 결정되지 않은 경우는 존재한다. 만약 누군가 이긴 상태라면, 가장 왼쪽 바둑알의 위치를 출력해야 한다. 단, 위아래로 오목이 완성된다면 가장 위쪽 바둑알의 위치를 출력해야 한다. 6개 이상으로 연결된 경우는 오목으로 치지 않는다.

접근 방법

왼쪽 위에서부터 순서대로 탐색하면서 바둑알의 위치를 찾습니다. 바둑알이 존재하는 칸이라면, 총 8방향으로 탐색을 해서 바둑알의 수를 세어줍니다. 그리고, 서로 정 반대 방향으로 탐색한 경우끼리 더해서 오목의 조건에 해당하는지 판별해줍니다. 만약 오목의 조건에 해당된다면, 그에 속한 바둑알들을 모두 저장해준 뒤에 정렬해서 첫번째 바둑알을 출력해주면 됩니다.

코드

#include <bits/stdc++.h>

using namespace std;

int board[20][20], dir[8][2] = { {1, 1}, {0, 1}, {-1, 1}, {1, 0}, {-1, -1}, {0, -1}, {1, -1}, {-1, 0} };
pair<int, int> ans;

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

int func(vector<pair<int, int>>& v, int r, int c, int ball, int direction, int len) {
	int nr = r + dir[direction][0], nc = c + dir[direction][1];

	if (nr > 19 || nr < 1 || nc > 19 || nc < 1 || board[nr][nc] != ball)
		return len;

	v.push_back({ nr, nc });
	return func(v, nr, nc, ball, direction, len + 1);
}

bool check(int ball) {
	for (int i = 1; i <= 19; i++) {
		for (int j = 1; j <= 19; j++) {
			if (board[i][j] == ball) {
				for (int k = 0; k < 4; k++) {
					vector<pair<int, int>> tmp;
					tmp.push_back({ i, j });

					if (func(tmp, i, j, ball, k, 1) + func(tmp, i, j, ball, k + 4, 1) == 6) {
						sort(tmp.begin(), tmp.end(), compare);
						ans = tmp[0];
						return true;
					}
				}
			}
		}
	}

	return false;
}

int main(void) {
	for (int i = 1; i <= 19; i++)
		for (int j = 1; j <= 19; j++)
			cin >> board[i][j];

	if (check(1)) {
		cout << 1 << '\n';
		cout << ans.first << ' ' << ans.second << '\n';
	}
	else if (check(2)) {
		cout << 2 << '\n';
		cout << ans.first << ' ' << ans.second << '\n';
	}
	else
		cout << 0 << '\n';

	return 0;
}