백준 : 7682

https://www.acmicpc.net/problem/7682

7682번: 틱택토

 

하나의 쿼리를 할때마다 유효성을 판단하는것은 메모리초과 or 시간 초과를 야기시킨다.

쿼리를 진행하기전에 모든 경우의수를 조사하다. 실제로 경우의수 < 9! 미만이다. 중간에 틱택톡을 완성하는 경우에는 그뒤의 경우를 포함하지 않으므로..

package algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
 
public class B7682 {
 
    static int[][] check = { { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 0, 3, 6 }, { 1, 4, 7 }, { 2, 5, 8 }, { 0, 4, 8 },
            { 2, 4, 6 } };
    static int endCnt;
    static char[] map = new char[9];
 
    static HashMap<String, String> hash = new HashMap<String, String>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
 
        DFS(".........".toCharArray(), 0);
        
        while (true) {
            map = br.readLine().toCharArray();
            if (map[0] == 'e')
                break;
 
            boolean answer = false;
 
            if (hash.containsKey(String.valueOf(map))) {
                answer = true;
            }
 
            if (answer) {
                sb.append("valid\n");
            } else {
                sb.append("invalid\n");
            }
 
        }
        System.out.print(sb.toString());
    }
 
    public static void DFS(char thisMap[], int cnt) {
        if (cnt == 9) {
            hash.put(String.valueOf(thisMap), "valid");
            return;
        }
 
        for (int i = 0; i < 8; i++) {
            if (thisMap[check[i][0]] != '.' && thisMap[check[i][0]] == thisMap[check[i][1]]
                    && thisMap[check[i][0]] == thisMap[check[i][2]]) {
                hash.put(String.valueOf(thisMap), "valid");
                return;
            }
        }
        
        for(int i=0;i<9;i++) {
            if (thisMap[i] != '.')
                continue;
            thisMap[i] = cnt % 2 == 0 ? 'X' : 'O';
            DFS(thisMap, cnt + 1);
            thisMap[i] = '.';
        }
    }
}