boj, 백준 ) 2615 오목

1. 문제 링크

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

2615번: 오목

2. 문제 개요

 지금 주어진 게임(상태)가 누구의 승리인지 판별하는 프로그램 제작.

 

3. 문제 힌트

 6개가 될 경우 어떻게 구별할것인가? -> 5개를 찾았을 때 그것이 6개의 부분집합이 아님을 어떻게 구별?

 가로 세로 대각선의 경우의수

 

4. 문제 풀이

 왼쪽에서 오른쪽, 위에서 아래쪽으로 탐색을 했다.

 발생하는 경우의 수는 

 (1) 가로 : 왼쪽에서 오른쪽

 (2) 세로 : 위에서 밑으로

 (3,4) 대각선 : 왼쪽 위에서 오른쪽 밑으로. 왼쪽 아래에서 오른쪽 위로.

 총 4가지로 정하고 탐색하였다.

 

 매 좌표마다 (1,1) (1,2)... 위의 4가지 방법을 탐색한다. 물론 범위를 벗어나면 연산하지 않도록 에러 처리를 해준다.

 (코드에서는 2번 에러 처리함.. 필요 없는데 안 지움, 함수 내부에서 1번 호출 시 1번)

 

 조건에 맞는 5개의 연속된 돌을 찾으면 탐색을 멈추고 출력하도록 했다.

 

5. 코드

#include <cstdio>
#include <algorithm>
using namespace std;

int map[20][20]; // 1 ~ 19

//only right side. because it searches from left to right side.
bool row_right(int pivot, int y, int x)
{
	bool retval = true;

	//check 5
	for (int i = 1; i < 5; ++i)
	{
		int curx = x + i;
		int cury = y;
		
		if (curx > 19)	return false;

		if (pivot != map[cury][curx])
			retval = false;
	}

	//check 6
	if (retval == true)
	{
		int curx = x + 5;
		int cury = y;

		if (curx <= 19)	
			if (pivot == map[cury][curx])
				retval = false;

		curx = x - 1;
		if (curx >= 1)
		if (pivot == map[cury][curx])
			retval = false;

	}

	return retval;
}

bool col_down(int pivot, int y, int x)
{
	bool retval = true;

	//check 5
	for (int i = 1; i < 5; ++i)
	{
		int curx = x;
		int cury = y + i;

		if (cury > 19)
			return false;

		if (pivot != map[cury][curx])
			retval = false;
	}

	//check 6
	if (retval == true)
	{
		int curx = x;
		int cury = y + 5;

		if (cury <= 19)
			if (pivot == map[cury][curx])
				retval = false;

		cury = y - 1;
		if (cury >= 1)
			if (pivot == map[cury][curx])
				retval = false;
	}
	return retval;
}

bool diag_rightdown(int pivot, int y, int x)
{
	bool retval = true;

	//check 5
	for (int i = 1; i < 5; ++i)
	{
		int curx = x + i;
		int cury = y + i;

		if (cury > 19 || curx > 19)
			return false;

		if (pivot != map[cury][curx])
			retval = false;
	}

	//check 6
	if (retval == true)
	{
		int curx = x + 5;
		int cury = y + 5;

		if (cury <= 19 && curx <= 19)	
			if (pivot == map[cury][curx])
				retval = false;

		cury = y - 1;
		curx = x - 1;
		if (cury >= 1 && curx >= 1)
			if (pivot == map[cury][curx])
				retval = false;
	}
	return retval;
}

bool diag_rightup(int pivot, int y, int x)
{
	bool retval = true;

	//check 5
	for (int i = 1; i < 5; ++i)
	{
		int curx = x + i;
		int cury = y - i;

		if (cury < 1 || curx > 19)
			return false;

		if (pivot != map[cury][curx])
			retval = false;
	}

	//check 6
	if (retval == true)
	{
		int curx = x + 5;
		int cury = y - 5;

		if (cury >= 1 && curx <= 19)
			if (pivot == map[cury][curx])
				retval = false;

		curx = x - 1;
		cury = y + 1;

		if (cury <= 19 && curx >= 1)
			if (pivot == map[cury][curx])
				retval = false;
	}
	return retval;
}
int main()
{
	bool isfind = false;

	int retx=0, rety=0;
	int winstone = 0;

	for (int i = 1; i <= 19; ++i)
		for (int j = 1; j <= 19; ++j)
			scanf("%d", &map[i][j]);

	for (int i = 1; i <= 19; ++i)
		for (int j = 1; j <= 19; ++j)
		{
			if (isfind == true)	break;

			bool chk_row = false;
			bool chk_col = false;
			bool chk_diag = false;
			bool chk_diag2 = false;
			if (map[i][j] != 0)
			{
				if( j <=15 )
					chk_row = row_right(map[i][j], i, j);
				if (i <= 15)
					chk_col = col_down(map[i][j], i,j);
				if (i <= 15 && j <= 15)
					chk_diag = diag_rightdown(map[i][j], i, j);
				if(i>=5 && j<=15)
					chk_diag2 = diag_rightup(map[i][j], i, j);
				if (chk_row || chk_col || chk_diag || chk_diag2)
				{
					rety = i, retx = j;
					winstone = map[i][j];
					isfind = true;
				}
			}
		}

	if (isfind == false)
	{
		printf("0\n");
	}
	else
	{
		printf("%d\n", winstone);
		printf("%d %d\n", rety, retx);
	}
	return 0;
}

 

지적, 댓글 언제나 환영입니다~