[BOJ] 2615번_오목_브루트포스 (C++)

[문제]

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

오목의 승패를 가리는 프로그램을 만드는 문제이다. 입력으로 바둑판의 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 아니면 아직 승부가 결정되지 않았는지를 판단해야한다. 당연히 여섯 알 이상이 연속적으로 놓인 경우(육목)에는 이긴 것이 아니다.

[사용 알고리즘]

브루트포스

[풀이 핵심]

• 오목은 19*19인 바둑판에서 진행되므로 모든 경우의 수를 판단하는 브루트포스 알고리즘으로 해결할 수 있다.
• 이겼을 경우에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알을 출력해야하므로 오목인지 검사하는 방향을 오른쪽 대각선 위, 오른쪽, 오른쪽 대각선 아래, 아래 이렇게 총 4가지로 하는 것이 편하다. (검사를 시작하는 돌이 무조건 가장 왼쪽에 있는 바둑알이 됨.)
• DFS기법을 이용하여 검은돌 또는 흰돌일 경우 오목인지 판단한다.
• 오른쪽 대각선 위로 바둑돌이 5개가 있더라도 왼쪽 대각선 아래를 검사해줘야한다. 왜냐하면 바둑판을 탐색하는 방향이 왼쪽에서 오른쪽으로, 위에서 아래이므로 왼쪽 대각선 아래의 돌 때문에 육목이 되는 경우가 발생하기 때문이다.

[코드]

//boj2615번_오목_브루트포스 알고리즘

#include<iostream>

using namespace std;

int graph[20][20];
bool visited[20][20][5];

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

int cnt;

void DFS(int x, int y, int dir) {
	visited[x][y][dir] = true;

	int next_x = x + dx[dir];
	int next_y = y + dy[dir];

	if (next_x > 0 && next_x <= 19 && next_y > 0 && next_y <= 19) {
		if (graph[x][y] == graph[next_x][next_y]) {
			cnt++;
			DFS(next_x, next_y, dir);
		}
	}
}

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

	for (int i = 1; i <= 19; i++) {
		for (int j = 1; j <= 19; j++) {
			if (graph[i][j] == 1 || graph[i][j] == 2) {
				for (int k = 0; k < 4; k++) {
					if (!visited[i][j][k]) {
						cnt = 1;
						DFS(i, j, k);

						if (k == 0) {
							DFS(i + 1, j - 1, k);
						}

						if (cnt == 5) {

							cout << graph[i][j] << '\n';
							cout << i << " " << j;

							return 0;
						}
					}
				}
			}
		}
	}

	cout << 0;

	return 0;
}