트라이, 공간분할 트리, 깊이 우선 탐색, 너비 우선 탐색, 미니맥스

트라이(Trie)

---

탐색 트리 중 하나
어원 : re(trie)val(구분하기 위해 트리 -> 트라이 로 발음)
다른 이름으로 digital tree, prefix tree(이해에 도움되는 이름) 라고 부름

정의

어떤 집합 안에서 특정한 키를 찾을 때 사용
키는 문자열인 경우가 보통
노드 사이의 연결이 한 글자로 결정(노드 하나가 키 전부가 아님)
노드 위치 자체가 키를 정의(노드가 키 전체를 저장하지 않음)

용도

사전 데이터 저장(용량을 더 차지할 수 있으나 탐색 속도 향상)
해시 테이블 대신 사용
충돌이 없음
해시 테이블보다 최악의 경우가 더 빠름 O(k)
평균 O(1) 은 아님
표현하기 어려운 데이터 형태도 있음(float)

공간분할 트리

---

쿼드 트리(quadtree)

사분 트리
재귀적으로 2D 공간을 분할
각 노드가 4개의 자식을 가짐

옥 트리(octree)

재귀적으로 3D 공간을 분할
각 노드가 8개의 자식을 가짐 (쿼드 트리 4자식 x 앞/뒤, 현재 노드를 8개의 하위 상자로 나눔)
3D 프로그램에 종종 사용(마인크래프트 등...)

기타 공간분할 트리

BSP(binary space partitioning), R 트리, k-d 트리, 등...

깊이 우선 탐색(DFS : Depth First Search)

---

한 우물부터 깊히 판다
왼쪽 대신 오른쪽 먼저 탐색해도 됨
중위 순회와 비슷
스택으로 작성하기 좋음

장점

재귀 함수 호출로 간단히 구현 가능
보통 너비 우선 탐색(BFS) 보다 메모리 사용량이 적음(트리 구조에 따라 다를 수 있음)
캐시 메모리에 좀 더 친화적
병렬처리에 더 적합

public static void searchDepthFirst(Node node) {
    Stack<Node> stack = new Stack<>();
    stack.push(node);
    while (!stack.empty()) {
        Node next = stack.pop();
        System.out.println(next.getData());
        for (Node child : node.children) {
            stack.push(child);
        }
    }
}

너비 우선 탐색(BFS : Breadth First Search)

---

여러 우물을 동시에 같은 깊이로
현재 깊이의 이웃 노드들을 우선 방문
최단 경로 찾기에 적합
큐로 작성하기 좋음

장점

언제나 최소 깊이의 결과를 찾음
깊이가 무한인 트리에도 사용 가능

public static void searchBreadthFirst(Node node) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(node);
    while (!queue.isEmpty()) {
        Node next = queue.remove();
        System.out.println(next.getData());
        for (Node child : node.children) {
            queue.add(child);
        }
    }
}

미니맥스

---

최악의 경우 발생할 수 있는 손실을 최소화하려는 규칙
게임이론, 결정이론, 통계학, 철학 등에서 널리 사용
제로섬(zero-sum) 게임의 결정 알고리듬으로 적합(n 명이 참가하는 제로섬 게임이론에서 시작한 알고리듬)
운 같은 요소가 없어야 하며 운 까지 고려한 변형 알고리듬도 있음

성능

점수 계산 함수가 얼마나 뛰어난지
얼마나 깊이 볼 수 있는지
이미 방문했던 노드는 다시 깊이 들어갈 필요가 없음
지금 보고 있는 노드가 이전에 본 것보다 별로인 것 같으면 중단(알파-베타 가지치기)

TicTacToe

재귀함수로 표현한 미니맥스 알고리듬 틱택토

public class Move {
    private int index;
    private int score;

    public Move(final int index, final int score) {
        this.index = index;
        this.score = score;
    }

    public int getIndex() {
        return this.index;
    }

    public int getScore() {
        return this.score;
    }
}

public enum Player {
    X, O
}

public class TicTacToe {
    public static final int BOARD_SIZE = 9;

    private TicTacToe() {}

    public static int getBestMoveIndex(final Player[] board, final Player player) {
        assert (board.length == BOARD_SIZE);

        //opponent : 상대
        Player opponent = player == Player.O
                ? Player.X : Player.O;
        Move move = getBestMoveRecursive(board, player, opponent, player);
        return move.getIndex();
    }

    private static Move getBestMoveRecursive(Player[] board, Player player, Player opponent, Player turn) {
        assert (board.length == BOARD_SIZE);

        if (haswon(board, opponent)) {
            return new Move(-1, -10);
        }

        if (haswon(board, player)) {
            return new Move(-1, 10);
        }

        ArrayList<Integer> availableIndexes = getEmptyIndexes(board);
        if (availableIndexes.isEmpty()) {
            return new Move(-1, 0);
        }

        ArrayList<Move> moves = new ArrayList<>();

        for (int i = 0; i < availableIndexes.size(); ++i) {
            int index = availableIndexes.get(i);

            Player[] newBoard = copyBoard(board);

            newBoard[index] = turn;

            Player nextPlayer = turn == player
                    ? opponent : player;

            int score = getBestMoveRecursive(newBoard, player, opponent, nextPlayer).getScore();

            Move move = new Move(index, score);

            moves.add(move);
        }

        if (turn == player) {
            return getMaxScoreMove(moves);
        }

        return getMinScoreMove(moves);
    }

    private static Move getMinScoreMove(ArrayList<Move> moves) {
        assert (!moves.isEmpty());

        Move bestMove = moves.get(0);
        for (int i = 0; i < moves.size(); ++i) {
            if (moves.get(i).getScore() < bestMove.getScore()) {
                bestMove = moves.get(i);
            }
        }

        return bestMove;
    }

    private static Move getMaxScoreMove(ArrayList<Move> moves) {
        assert (!moves.isEmpty());

        Move bestMove = moves.get(0);
        for (int i = 0; i < moves.size(); ++i) {
            if (moves.get(i).getScore() > bestMove.getScore()) {
                bestMove = moves.get(i);
            }
        }

        return bestMove;
    }

    private static Player[] copyBoard(Player[] board) {
        assert (board.length == BOARD_SIZE);

        Player[] newBoard = new Player[board.length];

        for (int i = 0; i < board.length; ++i) {
            newBoard[i] = board[i];
        }

        return newBoard;
    }

    private static ArrayList<Integer> getEmptyIndexes(Player[] board) {
        assert (board.length == BOARD_SIZE);

        ArrayList<Integer> indexes = new ArrayList<>();

        for (int i = 0; i < board.length; ++i) {
            if (board[i] == null) {
                indexes.add(i);
            }
        }

        return indexes;
    }

    private static boolean haswon(Player[] board, Player player) {
        assert (board.length == BOARD_SIZE);

        return (board[0] == player && board[1] == player && board[2] == player
                || board[3] == player && board[4] == player && board[5] == player
                || board[6] == player && board[7] == player && board[8] == player
                || board[0] == player && board[3] == player && board[6] == player
                || board[1] == player && board[4] == player && board[7] == player
                || board[2] == player && board[5] == player && board[8] == player
                || board[0] == player && board[4] == player && board[8] == player
                || board[2] == player && board[4] == player && board[6] == player);
    }
}