https://www.acmicpc.net/problem/7682
문제
입력에 주어진 상태가 틱택토게임이 정상적으로 끝난 상태인지 묻는 문제였다.
틱택토게임판의 크기가 3*3의 작은 크기임을 이용해서 풀어야겠다고 생각했다.
테스트케이스를 그림으로 그리면서 invalid인 이유를 써내려갔다.
그림을 보면서 규칙을 찾을 수 있었다.
풀이
X가 항상 먼저 공격하므로
무조건 X의 개수가 3~5개이고 Y의 개수가 2~4개여야 한다.
처음 이 조건이 만족되지 않으면 바로 invalid이다.
그 다음으로는 그 경기가 끝이 났는지 판별했다. X의 개수와 Y의 개수, 빈 공간의 개수를 세면서 빈공간이 하나도 없으면 게임이 끝날 수 있다.
또한 그 전에 누군가가 승리한다면 게임이 끝날 수 있다.
- 모두 채워져서 게임이 끝났을 때
a. X = 5개, O = 4개로 끝나야 하고, O가 승리하지 않아야 한다. - 누군가가 승리했을 때
a. X가 승리했을 때 -> X가 O보다 하나 더 많아야 한다.
b. Y가 승리했을 때 -> X와 O의 개수가 같아야 한다.
c. 동시에 승리하면 안된다.
위의 조건을 만족하지 않으면 모두 invalid로 취급한다.
코드
map = new char[3][3];
int x = 0;
int o = 0;
int dot = 0;
for (int i = 0; i < 9; i++) {
map[i / 3][i % 3] = s.charAt(i);
if (s.charAt(i) == 'X') x++;
if (s.charAt(i) == 'O') o++;
if (s.charAt(i) == '.') dot++;
}X, O, .의 개수를 센다
if (x > 5 || x < 3 || o > 4 || o < 2){ System.out.println("invalid"); return;}
만약 있을 수 없는 개수이면 바로 invalid
// 모두 채워졌을 경우
if (dot == 0 && x == 5 && o == 4) {
// O 이 이기지 않아야 함
if (judge('O')) {
System.out.println("invalid");
return;
}
System.out.println("valid");
return;
}모두 채워졌을 경우이다.
// 누군가 이겼을 경우
// X가 이겼을 때
if (judge('X') && !judge('O')) {
if(x == o + 1) {
System.out.println("valid");
return;
}
} else if (!judge('X') && judge('O')) {
if (x == o) {
System.out.println("valid");
return;
}
}
누군가 승리했을 경우이다.
이 외의 나머지는 전부 invalid를 출력한다.
전체코드
package baekjoon._7682;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static char[][] map;
public static void input() {
FastReader fr = new FastReader();
while (true) {
String s = fr.nextLine();
if (s.equals("end")) return;
pro(s);
}
}
public static void pro(String s) {
map = new char[3][3];
int x = 0;
int o = 0;
int dot = 0;
for (int i = 0; i < 9; i++) {
map[i / 3][i % 3] = s.charAt(i);
if (s.charAt(i) == 'X') x++;
if (s.charAt(i) == 'O') o++;
if (s.charAt(i) == '.') dot++;
}
if (x > 5 || x < 3 || o > 4 || o < 2){ System.out.println("invalid"); return;}
// 경기 끝났는지 확인
// 모두 채워졌을 경우
if (dot == 0 && x == 5 && o == 4) {
// o 이 이기지 않아야 함
if (judge('O')) {
System.out.println("invalid");
return;
}
System.out.println("valid");
return;
}
// 누군가 이겼을 경우
// X가 이겼을 때
if (judge('X') && !judge('O')) {
if(x == o + 1) {
System.out.println("valid");
return;
}
} else if (!judge('X') && judge('O')) {
if (x == o) {
System.out.println("valid");
return;
}
}
System.out.println("invalid");
}
public static boolean judge(char c) {
for(int i=0; i<3; i++) {
if(map[i][0] == c && map[i][1] == c && map[i][2] == c) {
return true;
}
}
// 세로
for(int i=0; i<3; i++) {
if(map[0][i] == c && map[1][i] == c && map[2][i] == c) {
return true;
}
}
// 대각선
if(map[0][0] == c && map[1][1] == c && map[2][2] == c) {
return true;
}
if(map[2][0] == c && map[1][1] == c && map[0][2] == c) {
return true;
}
return false;
}
public static void main(String[] args) {
input();
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreTokens()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
Double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}
느낀점
처음엔 BFS나 DFS로 승리했는지 판단해야하나 했는데 3*3인 맵을 적극반영해 손쉽게 O(3)으로 판단가능했다.
또한 BFS, DFS는 같은 방향으로 나가야 하는 데 코드짜기가 복잡
문제의 특성을 잘 파악하고 문제를 풀어나가자
DevOps Engineer