Computer Science/Algorithm Problem

백준] 2615 - 오목(KOI 2003 초등부, ACM-ICPC Regionals)

TwinParadox 2019. 1. 12. 18:43
728x90

시간 제한 : 1초

메모리 제한 : 128MB




입력

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




출력

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




소스코드

#include <iostream>
using namespace std;
int board[19][19], boardSize = 19;
int dir[4][2] = { {1,0},{1,1},{0,1},{-1,1} };
int main(void)
{
	int ans1, ans2, ansWin;
	ans1 = ans2 = ansWin = -1;

	for (int i = 0; i < boardSize; i++)
		for (int j = 0; j < boardSize; j++)
			cin >> board[i][j];

	for (int i = 0; i < 4; i++)
	{
		for (int j = 0; j < boardSize; j++)
		{
			for (int k = 0; k < boardSize; k++)
			{
				if (board[j][k] == 0)
					continue;

				int pj = j - dir[i][0], pk = k - dir[i][1];
				if (board[pj][pk] == board[j][k])
					continue;

				int nj = j, nk = k, cnt = 1;
				while (1)
				{
					nj += dir[i][0];
					nk += dir[i][1];

					if (nj < 0 || nj >= boardSize || nk < 0 || nk >= boardSize)
						break;

					if (board[nj][nk] != board[j][k])
						break;

					cnt++;
				}
				if (cnt == 5)
				{
					ans1 = j;
					ans2 = k;
					ansWin = board[j][k];
				}
			}
		}
	}

	if (ansWin == -1)
		cout << 0;
	else
		cout << ansWin << '\n' << ans1 + 1 << ' ' << ans2 + 1;
}




Tip

오목을 한 번쯤이라도 짜본 사람이라면 쉽게 풀 수 있는 문제다. 원초적으로 특정 돌을 기준으로 오목이 완성되는지 확인하는 절차를 진행해서 승부를 판단한다.


728x90