[AlgoSpot] 틱택토

문제 설명

알고리즘 문제 해결 전략 - 동적 계획법
https://algospot.com/judge/problem/read/TICTACTOE

문제 풀이

• 동적 계획법 문제이다.
• 풀이에 사용된 유틸 및 메인 함수는 다음과 같다

  • char isFinish(char[][] map) : 현재 보드 상태에서 이기는 말 모양 리턴, 이기는 말이 없으면 'n' 리턴
  • int createCacheIndex(char[][] map) : 현재 보드를 캐시 배열 인덱스로 변환
  • int canWin(char[][] map, char turn) : turn 말을 놓았을 때 이기는 경우 1, 비기는 경우 0, 지는 경우 -1 리턴.

• 위에서 createCacheIndex의 경우 캐시의 인덱싱을 위해 쓰이는데 보드의 각칸의 상태를 3가지 (o, x, .)로 둬서 보드를 3진수로 변환하는 함수이다.
• 위 함수 중 가장 중요한 canWin함수에서 사용된 점화식 아이디어는 현재 보드에 turn말을 놓았을 때 다음 canWin(변화된 보드, 상대방말)이 지는 경우(turn말이 이기는 경우)가 있을 경우 1(turn말이 이기는 경우)을 리턴이다. (자세한 내용은 코드 참조)

소스 코드 (JAVA)

import java.util.Scanner;

public class Main {
    public static int C;
    public static char[][] map = new char[3][3];
    public static int[] cache = new int[19684];
    //어떤 말이던 이기는 상태일 경우 이기는 말 리턴
    //아니면 'n' 리턴
    public static char isFinished(char[][] map) {
        //가로
        for (int i = 0; i < 3; i++) {
            if (map[i][0] != '.' && map[i][1] == map[i][0] && map[i][2] == map[i][0])
                return map[i][0];
        }
        //세로
        for (int i = 0; i < 3; i++) {
            if (map[0][i] != '.' && map[1][i] == map[0][i] && map[2][i] == map[0][i])
                return map[0][i];
        }
        //대각선
        if (map[0][0] != '.' && map[1][1] == map[0][0] && map[2][2] == map[0][0]) return map[0][0];
        if (map[2][0] != '.' && map[1][1] == map[2][0] && map[0][2] == map[2][0]) return map[2][0];
        return 'n';
    }

    //현재 map 상태로 cache를 만듬
    //'.' : 0, 'X' : 1, 'O' : 2
    public static int createCacheIndex(char[][] map) {
        int ret = 0; //총 값
        int num = 1; //자리수
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (map[i][j] == 'x') ret += (num * 1);
                else if (map[i][j] == 'o') ret += (num * 2);
                num *= 3;
            }
        }
        return ret;
    }

    //turn이라는 말을 놓았을때
    //turn이 이기면 1
    //비기면 0
    //turn이 지면 -1 리턴
    public static int canWin(char[][] map, char turn) {
        //기저 사례
        char res = isFinished(map);
        if (res != 'n') {
            if (res == turn) return 1;
            else return -1;
        }
        //다이나믹 프로그래밍
        int cacheIndex = createCacheIndex(map);
        if (cache[cacheIndex] != -2) return cache[cacheIndex];

        int minValue = 2;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (map[i][j] == '.') {
                    map[i][j] = turn;
                    minValue = Math.min(minValue, canWin(map, turn == 'o' ? 'x' : 'o'));
                    map[i][j] = '.';
                }
            }
        }

        if (minValue == 2 || minValue == 0) cache[cacheIndex] = 0;
        else cache[cacheIndex] = -minValue;
        return cache[cacheIndex];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        C = sc.nextInt();
        for (int c = 0; c < C; c++) {
            for (int i = 0; i < 3; i++) {
                String tmp = sc.next();
                map[i] = tmp.toCharArray();
            }
            //초기화
            for (int i = 0; i < 19684; i++)
                cache[i] = -2;
            //누구 턴인지 찾기
            int aCnt = 0;
            int bCnt = 0;
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (map[i][j] == 'x') aCnt++;
                    if (map[i][j] == 'o') bCnt++;
                }
            }
            int result;
            if (aCnt > bCnt) result = canWin(map, 'o');
            else result = canWin(map, 'x');

            if (result == -1) System.out.println(aCnt > bCnt ? 'x' : 'o');
            else if (result == 0) System.out.println("TIE");
            else System.out.println(aCnt > bCnt ? 'o' : 'x');
        }
        return;
    }
}