프로그래머스 - 혼자서 하는 틱택토

문제 설명

선공과 후공의 순서로 틱택토 게임을 한다.

주어진 보드가 주어졌을 때 규칙을 지키면서 제대로 이행한 보드인지 판별하는 문제이다.

규칙을 잘 지키면서 했으면 1을, 안지켰으면 0을 리턴한다.

주의사항

규칙의 반례를 직접적으로 찾아 나가야한다.

1. o-x를 뺀 개수는 무조건 0이 나오거나 1이 나와야 한다. [선공과 후공의 관계이기 때문에]
2. o와 x가 둘다 틱택토를 완성할 수는 없다 [그러면 o가 먼저 틱택토 나오고 끝나야 한다]

3) o만 틱택토를 완성했다면, o-x의 차이는 무조건 1이여야 한다 [선공과 후공의 관계이기 때문에]

4) x만 틱택토를 완성했다면, o-x의 차이는 반드시 0이나와야 한다. [선공과 후공의 관계이기 때문에]

3,4을 찾는데 엄청 오래걸렸다..

풀이

static final int VIOLATION = 0;
	static final int FOLLOW_RULES = 1;
	int n, m;
	char map[][];

	public int solution(String[] board) {
		n = board.length;
		m = board[0].length();

		map = new char[n][m];
		for (int i = 0; i < n; i++) {
			map[i] = board[i].toCharArray();
		}

		if (isValidCount(map) & isLastValid(map)) {
			return FOLLOW_RULES;
		}

		return VIOLATION;
	}

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

	public boolean isValidCount(char[][] map) {
		int cnt = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 'O') {
					cnt++;
				} else if (map[i][j] == 'X') {
					cnt--;
				}
			}
		}
		// x개수 <= o의개수 만족해야함 그리고 그 둘의 차이는 무조건 0또는 1이여 한다.
		return cnt == 0 || cnt == 1;
	}

	public boolean isLastValid(char[][] map) {
		int ticTakToe1 = 0;
		int ticTakToe2 = 0;
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {

				if (map[i][j] == 'O' || map[i][j] == 'X') {
					char pivot = map[i][j];
					for (int k = 0; k < 8; k++) {
						int ny = i + dy[k];
						int nx = j + dx[k];

						int nny = ny + dy[k];
						int nnx = nx + dx[k];

						if (isOutOfRange(ny, nx) || isOutOfRange(nny, nnx))
							continue;

						if (pivot == map[ny][nx] && pivot == map[nny][nnx]) {
							if (pivot == 'O') {
								ticTakToe1++;
							} else {
								ticTakToe2++;
							}
						}

						if (ticTakToe1 > 0 && ticTakToe2 > 0) { // 둘다 이긴경우 있을 수 없다. 누군가는 반드시 먼저 승리하고 끝나야 한다.
							return false;
						} else if (ticTakToe1 > ticTakToe2) { // 선공이 이긴경우는 무조건 1개 더 많아야한다.
							if (!isDiffOne()) {
								return false;
							}
						} else if (ticTakToe2 > ticTakToe1) { // x가 이길 때는 반드시 o와 개수가 같아야 한다 [o가 선공이기 때문에]
							if (!isDiffZero()) {
								return false;
							}

						}
					}
				}
			}
		}

		return true;
	}

	public boolean isDiffOne() {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 'O')
					cnt++;
				else if (map[i][j] == 'X')
					cnt--;
			}
		}

		return cnt == 1;
	}

	public boolean isDiffZero() {
		int cnt = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (map[i][j] == 'O')
					cnt++;
				else if (map[i][j] == 'X')
					cnt--;
			}
		}

		return cnt == 0;
	}

	public boolean isOutOfRange(int ny, int nx) {
		return ny < 0 || nx < 0 || ny >= n || nx >= m;
	}