백준 2615 오목 c++ (완전탐색)

문제 출처 : https://www.acmicpc.net/problem/2615

2615번: 오목

문제

오목은 바둑판에 검은 바둑알과 흰 바둑알을 교대로 놓아서 겨루는 게임이다. 바둑판에는 19개의 가로줄과 19개의 세로줄이 그려져 있는데 가로줄은 위에서부터 아래로 1번, 2번, ... ,19번의 번호가 붙고 세로줄은 왼쪽에서부터 오른쪽으로 1번, 2번, ... 19번의 번호가 붙는다.

위의 그림에서와 같이 같은 색의 바둑알이 연속적으로 다섯 알을 놓이면 그 색이 이기게 된다. 여기서 연속적이란 가로, 세로 또는 대각선 방향 모두를 뜻한다. 즉, 위의 그림은 검은색이 이긴 경우이다. 하지만 여섯 알 이상이 연속적으로 놓인 경우에는 이긴 것이 아니다.

입력으로 바둑판의 어떤 상태가 주어졌을 때, 검은색이 이겼는지, 흰색이 이겼는지 또는 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오. 단, 검은색과 흰색이 동시에 이기거나 검은색 또는 흰색이 두 군데 이상에서 동시에 이기는 경우는 입력으로 들어오지 않는다.

입력

19줄에 각 줄마다 19개의 숫자로 표현되는데, 검은 바둑알은 1, 흰 바둑알은 2, 알이 놓이지 않는 자리는 0으로 표시되며, 숫자는 한 칸씩 띄어서 표시된다.

출력

첫줄에 검은색이 이겼을 경우에는 1을, 흰색이 이겼을 경우에는 2를, 아직 승부가 결정되지 않았을 경우에는 0을 출력한다. 검은색 또는 흰색이 이겼을 경우에는 둘째 줄에 연속된 다섯 개의 바둑알 중에서 가장 왼쪽에 있는 바둑알(연속된 다섯 개의 바둑알이 세로로 놓인 경우, 그 중 가장 위에 있는 것)의 가로줄 번호와, 세로줄 번호를 순서대로 출력한다.

알고리즘 분류

• 구현
• 브루트포스 알고리즘

풀이

완전탐색에서도 그래프에 가까운 문제이다.

출력은 이긴 돌의 숫자와, 오목의 가장 왼쪽에 있는 돌의 좌표, 오목이 세로로 완성된 경우 가장 위에 있는 돌의 좌표를 출력하면 된다.

오목이 완성된 경우를 확인하기 위해, dfs를 이용하여 시작 좌표를 기준으로 한 방향으로 0이나 다른 돌을 만날 때까지 탐색하였고, 그 수가 5인 경우에만 이긴 경우다.(6이상인 경우를 조심하자)

오목의 탐색 방향은, 가장 왼쪽, 혹은 위의 돌의 좌표를 구해야 하므로, 돌의 방향 검사는, 위에서 아래로, 왼쪽에서 오른쪽으로, 우상향대각, 우하향 대각 총 4가지 방향만 검사하면된다.

 

전체적인 풀이는, 그래프를 입력받고, 0,0부터 세로로, 즉 0,0~18,0 -> 0,1 ~18,1 -> ... -> 0,18 > 18,18을 검사하면서, 1이나 2 돌을 만나면, visited[19][19][dir][2] 배열을 이용해, 4가지 방향에 대한 탐색을 시작하는데, 현재 방향이 이미 방문했다면 탐색을 하지 않음으로써 돌이 6개 이상인 경우에 중간부터 시작하여 5개가 나오는 경우를 방지한다.

//visited[j][i][dir][k] 는 j,i좌표의 dir 방향의 k돌이 방문되었는지를 저장한다.

만약 오목이 완성된 경우, 그래프의 인덱스는 0부터 시작했으므로, 돌과 j+1, i+1을 출력한 후 프로그램을 종료한다.

만약 이중 for문 안에서 프로그램이 종료되지 않았다면, 오목이 완성될 수 없다는 의미로 0을 출력한다.

코드

#include <iostream>
#define MAX 19
using namespace std;

char graph[MAX][MAX];
int moving[4][2] = { {0,1},{1,0},{1,1},{-1,1} };
bool visited[MAX][MAX][4][2];

char dfs(int r, int c, int dir, char color, int cnt) {
	visited[r][c][dir][color - '1'] = true;
	int nR = r + moving[dir][0];
	int nC = c + moving[dir][1];
	if (nR < 0 || nR >= MAX || nC < 0 || nC >= MAX || graph[nR][nC] != color) {
		if (cnt == 5) {
			return color;
		}
		else {
			return '0';
		}
	}
	return dfs(nR, nC, dir, color, cnt + 1);
	
}

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

	for (int i = 0; i < MAX; i++) {
		for(int j=0; j<MAX;j++){
			cin>>graph[i][j];
		}
	}
	
	for (int i = 0; i < MAX; i++) {
		for (int j = 0; j < MAX; j++) {
			if (graph[j][i] != '0') {
				for (int dir = 0; dir < 4; dir++) {
					if (visited[j][i][dir][graph[j][i] - '1'])continue;
					if (dfs(j, i, dir, graph[j][i], 1) != '0') {
						cout << graph[j][i] << '\n' << j + 1 << ' ' << i + 1;
						return 0;
					}
				}
			}
		}
	}
		
	cout << 0;
	return 0;
}