[백준] 7682 - 틱택토 (자바 Java)

[Gold V] 틱택토 - 7682

문제 링크

성능 요약

메모리: 11412 KB, 시간: 72 ms

분류

백트래킹(backtracking), 구현(implementation)

문제 설명

틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 두 번째 사람이 O를 놓는다. 어느 때든지 한 사람의 말이 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하면 게임은 즉시 끝난다. 게임판이 가득 차도 게임은 끝난다.

게임판의 상태가 주어지면, 그 상태가 틱택토 게임에서 발생할 수 있는 최종 상태인지를 판별하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입력의 마지막에는 문자열 "end"가 주어진다.

출력

각 테스트 케이스마다 한 줄에 정답을 출력한다. 가능할 경우 "valid", 불가능할 경우 "invalid"를 출력한다.

---

풀이

분명 조건을 다 충족했다고 생각했는데 20퍼쯤에서 틀려서 if문을 바꿨더니 됐다.

잘못 구현한 부분은 if와 else에서 조건을 &&로 걸어서
XXO
XOO
OXX
의 경우 isO는 true, isX는 false지만 O의 개수보다 X가 많아서 false를 return해야 한다.

 

근데 조건을 if (isO && !isX && cntO == cntX) 라고 붙여서 이 경우를 충족하지 않는 경우 full로 인식하고 full의 경우에는 개수 조건을 충족해서 valid를 출력하였다.

 

다른 사람들의 코드가 모두 map이 가득 차 있는지 아닌지부터 검사하고 유효조건을 검사했는데, 나는 먼저 유효조건부터 검사해서 조건이 어긋났던 것 같다.

 

구현 자체는 어렵지 않은 문제인데, 조건을 꼼꼼하게 확인하는 게 중요한 문제인 것 같다!

package BOJ.Gold.g5;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class BOJ_7682_틱택토 {
	static char[][] map;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		while (true) {
			String input = br.readLine();
			if (input.equals("end"))
				break;
			map = new char[3][3];
			int cntO = 0;
			int cntX = 0;
			int empty = 0;
			for (int i = 0; i < 3; i++)
				for (int j = 0; j < 3; j++) {
					map[i][j] = input.charAt(i * 3 + j);
					switch (map[i][j]) {
					case 'O':
						cntO++;
						break;
					case 'X':
						cntX++;
						break;
					case '.':
						empty++;
						break;
					}
				}
			boolean isO = check('O');
			boolean isX = check('X');

			// empty - 조건을 충족했는지 체크
			if (empty == 0) {
				// full
				if (!isO && cntO + 1 == cntX)
					sb.append("valid").append("\n");
				else
					sb.append("invalid").append("\n");

			} else {
				// empty
				if (isO && !isX && cntO == cntX)
					sb.append("valid").append("\n");
				else if (!isO && isX && cntO + 1 == cntX)
					sb.append("valid").append("\n");

				else
					sb.append("invalid").append("\n");
			}
		}
		System.out.print(sb);
	}

	static boolean check(char c) {
		for (int i = 0; i < 3; i++) {
			if (map[i][0] == c && map[i][0] == map[i][1] && map[i][1] == map[i][2]) {
				return true;
			}
			if (map[0][i] == c && map[0][i] == map[1][i] && map[1][i] == map[2][i]) {
				return true;
			}
		}

		// 대각선 검사
		if (map[0][0] == c && map[0][0] == map[1][1] && map[1][1] == map[2][2]) {
			return true;
		}
		if (map[0][2] == c && map[0][2] == map[1][1] && map[1][1] == map[2][0]) {
			return true;
		}
		return false;
	}

}