문제
백준 : 7682
Lv 5
문제
틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 두 번째 사람이 O를 놓는다. 어느 때든지 한 사람의 말이 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하면 게임은 즉시 끝난다. 게임판이 가득 차도 게임은 끝난다.
게임판의 상태가 주어지면, 그 상태가 틱택토 게임에서 발생할 수 있는 최종 상태인지를 판별하시오.
입력
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입력의 마지막에는 문자열 "end"가 주어진다.
출력
각 테스트 케이스마다 한 줄에 정답을 출력한다. 가능할 경우 "valid", 불가능할 경우 "invalid"를 출력한다.
예제 입력 1
XXXOO.XXX
XOXOXOXOX
OXOXOXOXO
XXOOOXXOX
XO.OX...X
.XXX.XOOO
X.OO..X..
OOXXXOOXO
end
예제 출력 1
invalid
valid
invalid
valid
valid
invalid
invalid
invalid
문제 해설
해당 판이 가능한 판인지를 판단하는 것이다.
예제를 보면
XXX
OO.
XXX
이 경우 x 빙고가 2개가 나오기 때문에 invalid 하다.
하나의 빙고가 나오면 게임은 멈추기 때문이다.
X.O
O..
X..
이 경우는 아직 게임이 진행될 수 있으므로 최종 상태가 될 수 없다.
이런 식으로 게임의 최종 상태인지 아닌지를 구분한다.
풀이
이 문제에서는 특정 알고리즘이 쓰이지 않고 가능한 경우/ 가능하지 않은 경우의 조건을 잘 두는 것이 중요하다.
이 게임에서 invalid가 되는 경우는 아래와 같다.
1. 기본 턴 수 체크
게임 규칙을 보면 x가 먼저 시작하기 때문에
x의 개수 == o의 개수 혹은 x의 개수 = o의 개수 +1
가 되어야 한다.
2. 승리 여부 체크
x가 빙고가 되는 경우가 있는지, o가 빙고가 되는 경우가 있는지를 체크한다.
3. 승리 경우에 따라 count 체크
x가 이긴 경우에는 x의 개수가 o보다 더 많아야하고,
o가 이긴 경우에는 x의 개수와 o의 개수와 같아야 한다.
4. !xwin, !owin은 보드가 꽉 찬 상태만 가능
둘 다 이기지 않았는데 게임이 끝나는 경우는 보드가 꽉 찬 상태여야만 가능하다.
코드 구현
1. end가 나올 때까지 반복
while(!str.equals("end")) {
int xCount = 0;
int oCount = 0;
boolean valid = true;2. map 배열에 현재 상태 저장
저장하는 중에 x와 o의 카운트도 함께 센다.
//map 배열에 저
map = new char[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
map[i][j] = str.charAt(i * 3 +j);
//카운트 확인
if (map[i][j] == 'X') {
xCount += 1;
} else if(map[i][j] == 'O') {
oCount += 1;
}
}
}
3. 기본 턴 수 조건을 만족하는지 확인
o가 x보다 큰 경우는 없으므로, 해당 경우는 false로 처리
if (oCount > xCount ) {
valid = false;
}
4. 승리 여부 체크하는 메서드
//승리여부 체크
boolean xWin = checkWin('X', map);
boolean oWin = checkWin('O', map);
가로, 세로, 대각선에서 빙고가 나오는지 확인해준다.
private static boolean checkWin(char c, char[][] map) {
char target = c;
boolean bingo = false;
boolean flag = true;
//가로 검사
for (int i = 0; i < 3; i++) {
flag = true;
for (int j =0; j < 3; j++) {
if (map[i][j] != target) {
flag = false;
continue;
}
}
if (flag) {
bingo = true;
}
}
//세로 검사
for (int j = 0; j < 3; j++) {
flag = true;
for (int i =0; i < 3; i++) {
if (map[i][j] != target) {
flag = false;
continue;
}
}
if (flag) {
bingo = true;
}
}
//대각선 검사
flag = true;
for (int i =0; i < 3; i++) {
if (map[i][i] != target) {
flag = false;
}
}
if (flag) {
bingo = true;
}
flag = true;
for (int i =2; i >= 0; i--) {
if (map[i][2- i] != target) {
flag = false;
}
}
if (flag) {
bingo = true;
}
if (flag) {
bingo = true;
}
return bingo;
}5. 승리 여부에 따른 count 체크
//둘 다 승리하면 invalid
if (xWin && oWin) {
valid = false;
}
//x가 승리했는데, x의 값이 oCount +1이 아니면 invalid
if (xWin && (xCount != oCount +1)) {
valid = false;
}
//o가 승리했는데, x의 count가 oCount와 같지 않다면 invalid
if (oWin && (xCount != oCount)) {
valid = false;
}
//아무도 이기지 않았는데, 바둑판이 꽉 차지 않았다면 invalid
if (!oWin && !xWin && (xCount + oCount != 9)) {
valid = false;
}
6. 정답 출력
무한 루프가 나오지 않게 다음 입력값을 받아준다.
if (valid ) {
System.out.println("valid");
} else {
System.out.println("invalid");
}
str = sc.nextLine();