[BOJ] 16955 오목, 이길 수 있을까?

문제: www.acmicpc.net/problem/16955

 

문제는 "구사과의 돌(x)을 하나 더 뒀을 때, 가로/세로/대각선으로 x가 5개 이상 연속하는지"를 찾는 것이다.

 

문제 풀이:

• 모든 점에 대해, 그 점에서 오른쪽의 그림과 같이 4방향으로 5칸을 스캔한다.
• 5칸 안에 'o'가 존재하지 않고, 'x' 4개가 있다면 바로 1을 리턴해주면 된다.

 

주의!

처음에는 for(int k=0~5)가 끝나고 cnt('x'의 개수)가 4개이면 바로 1을 리턴해줘 계속 틀렸었다 ㅠㅠ

 

다음과 같은 경우가 발생할 수 있다.

즉, 현재 'x'를 4개 발견해도 다음에 놓을 곳이 바둑판을 넘어갈 수 있다는 사실을 명심하자!

 

 

 

 

 

 

 

 

소스 코드:

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

char arr[11][11];

bool func() {
	int cnt;
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			// ->
			if (j <= 5) {
				cnt = 0;
				for (int k = 0; k < 5; k++) {
					if (arr[i][j + k] == 'X') cnt++;
					else if (arr[i][j + k] == 'O') break;

					if (k == 4 && cnt >= 4) return true;
				}
			}
			
			// ↓
			if (i <= 5) {
				cnt = 0;
				for (int k = 0; k < 5; k++) {
					if (arr[i + k][j] == 'X') cnt++;
					else if (arr[i + k][j] == 'O') break;

					if (k == 4 && cnt >= 4) return true;
				}
			}
			
			// ↘
			cnt = 0;
			for (int k = 0; k < 5; k++) {
				if (i + k >= 10 || j + k >= 10) break;
				if (arr[i + k][j+k] == 'X') cnt++;
				else if (arr[i + k][j+k] == 'O') break;

				if (k == 4 && cnt >= 4) return true;
			}

			// ↗
			cnt = 0;
			for (int k = 0; k < 5; k++) {
				if (i - k <0 || j + k >= 10) break;
				if (arr[i - k][j + k] == 'X') cnt++;
				else if (arr[i - k][j + k] == 'O') break;

				if (k==4&&cnt >= 4) return true;
			}
			
		}
	}
	return false;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < 10; j++) {
			cin >> arr[i][j];
		}
	}

	if (func()) cout << "1";
	else cout << "0";

	return 0;
}