프로그래머스 | LV.2 혼자서 하는 틱택토 - 경우의 수 & 구현 or 완전탐색 문풀 (Java)

⬛ 프로그래머스 | LV.2 혼자서 하는 틱택토 - 경우의 수 & 구현

https://school.programmers.co.kr/learn/courses/30/lessons/160585

프로그래머스

문제 설명

---

💚문제 접근 방식

• 1차 제출 시에는 DFS 로 완전탐색하여 구현하고자 했다. 매번 O→X 의 규칙대로 번갈아 다음 깊이로 이동하되, 빙고일 경우는 안되도록 깊이 이동하면 된다고 생각했다 → 이 방식이 되긴 하는데, 실제로 구현 과정에서.. 애를 먹었다. (굳이 추천하지는 않는다. 다만, DFS로도 될 거 같은데 ? 란 생각이 들었다면 완전 잘못된 접근까지는 아니다. 이 문제의 경우 데이터 크기가 작기 때문에 이렇게 풀어도 통과한다. 그렇지만 구현이 빡세기 때문에 단순 구현으로 케이스 나누길 더 추천하다.)
• 2차 제출 시에는 O의 개수와 X의 개수에 대한 (불가능) 조건 케이스를 경우의 수로 쪼개서 짰고, 이 방식도 처음엔 실패를 했는데 내가 몇 가지 엣지 케이스를 놓쳤기 때문이었다. 엣지 케이스를 빠짐없이 고려해야 한다.

 X가 후공이지만 아래의 케이스처럼 먼저 승리할 수 있는 케이스도 있다.
⇒ 처음에는 O가 선공이라 반드시 O의 빙고만 있을 거라 생각했는데, (진짜 나도 생각이 개 짧다.)

O O .
X X X 
O O . 

[불가능한 경우의 수]

1) X 개수 > O 개수 : 불가능

→ O가 선공이기 때문에 X가 더 클 수 없고, X가 빙고가 돼서 끝나도 둘의 크기는 같다. 즉, X가 더 큰 케이스는 불가능하다.

2) O 개수 - X 개수 ≥ 2 : 불가능

→ O가 선공이라서 둘 차이는 1보다 작거나 같아야 한다. (X가 승리했을 때도 둘 차이는 같다.) 따라서 2이상 차이나는 것도 불가능하다.

3) O 먼저 빙고인 경우, O-X ≠ 1 : 불가능

→ O가 먼저 빙고여서 끝난 시점에는 O 선공이므로. 둘 차이는 반드시 1개여야 한다. 둘 차가 1과 다르다면 불가능하다.

4) X 먼저 빙고인 경우, O ≠ X : 불가능

→ X가 먼저 빙고돼서 끝난 시점에는 두 개수가 반드시 같아야 한다. 그렇지 않으면 불가능하다.

---

💚 제출 코드 | 경우의 수 & 단순 구현

import java.util.*;

class Solution {
    static char[][] map;
    //O 빙고 판별
    static boolean isBingGo(char c){ //현재값을 담으면 빙고 되는지 여부 판별 
        for(int i=0; i<3; i++){ 
            if(map[i][0] == c && map[i][1] == c && map[i][2] == c) return true;//행 빙고
            if(map[0][i] == c && map[1][i] == c  && map[2][i] == c) return true;//열 빙고 
        }
        //대각선 빙고
        if(map[1][1] == c){
            if(map[0][0] == c && map[2][2] == c) return true;
            if(map[0][2] == c&& map[2][0] == c) return true;
        }
        return false;
    }
   
    
    //솔루션 함수 
    public int solution(String[] board) {
        int Ocnt = 0;
        int Xcnt = 0;
        map = new char[3][3];
        
        for(int i = 0; i<3; i++){
            for(int j=0; j<3; j++){
                char tmp = board[i].charAt(j);
                if(tmp == 'O') Ocnt++;
                if(tmp == 'X') Xcnt++;
                map[i][j] = tmp;
            }
        }
        //(1) X 개수가 더 클 경우는 애초에 안됨 
        if(Xcnt > Ocnt) return 0;
        //(2) O 개수가 X 개수보다 2개이상 큰 경우도 불가능하다. (최대 1개 차이)
        if(Ocnt - Xcnt >= 2) return 0;
        //(3) O 가 빙고인데 X개수가 크거나 같은 건 말도 안됨 
        if(isBingGo('O') && Ocnt - Xcnt != 1) return 0;
        //(4) X가 (후공) 먼저 빙고 칠 경우, 둘 크기는 같아야 됨. O가 클 수 없음  말이 안됨 
        if(isBingGo('X') && Ocnt - Xcnt != 0) return 0;
        
        return 1;
    }
}

---

💚 [추가]  DFS 완전탐색 접근 시 코드

DFS도 구현 과정에서 애를 먹을 뿐이지 제대로만 구현하면 성공은 한다.

? DFS를 떠올린 이유

예제 설명을 보는데, 예제 1번의 케이스가 틱택토에서 나올 수 있는 케이스인지 따질 때, 각 좌표값을 기준으로 총 개수 4개까지 쭉이어 가는 듯이 설명했다. 이떄 아 ! 선공 O로 DFS를 시작한다면 조건따져가며 다음 깊이를 쭉 갔을 떄 끝까지 다다를 수 있다면 모두 가능한 케이스가 되는 구나 싶었다. 물론 내가 잘했다는 건 아니다. 걍 그래서 DFS도 떠올렸다. 

예제 1번 설명

예제 1번에 대한 DFS 완탐을 어떤 식으로 접근 사고해서 시도한 건지 표현한 흐름은 아래 그림과 같다.

예제 1번에 대한 DFS 완탐 시도 시 게임 정상 처리를 위 논리로 처리함

import java.util.*;

class Solution {
    private static final char FIRST_SYMBOL = 'O';
    private static final char SECOND_SYMBOL = 'X';
    private static final char EMPTY_SYMBOL = '.';

    // 선공, 후공 각각 돌 좌표(position) 을 list 형태로 가공
    // key : 바둑돌 character ('O', 'X')
    // value : position list
    private Map<Character, List<Position>> positionsMap;

    private int answer = 0; // dfs 를 재귀로 구현할거라, 매번 파라미터로 answer 넘겨주기 싫어서 전역으로 선언
    private char[][] board = new char[3][3]; // board 도 answer 와 같은 이유. + 더 편하게 char[][] 로 가공함

    public int solution(String[] board) {
        initBoard(board); // this.board 초기화
        initPositions(); // this.positionsMap 초기화

        dfs(FIRST_SYMBOL, new char[3][3]);
        return answer;
    }

    private void initBoard(String[] board) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                this.board[i][j] = board[i].charAt(j);
            }
        }
    }

    private void initPositions() {
        positionsMap = new HashMap<>();

        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (board[i][j] == EMPTY_SYMBOL) {
                    continue;
                }

                if (!positionsMap.containsKey(board[i][j])) {
                    positionsMap.put(board[i][j], new ArrayList<>());
                }

                positionsMap.get(board[i][j]).add(new Position(i, j));
            }
        }
    }

    // 재귀로 dfs 구현
    // symbol : 현재 턴에 둬야 할 바둑돌 순서를 나타냄 (선공차례인지, 후공차례인지 여부)
    // curBoard : dfs 로 재귀를 돌면서 만들어가는 바둑판
    private void dfs(char symbol, char[][] curBoard) {
        if (isBingo(curBoard)) { // 현재 턴에 두려고 보니 이미 빙고 상태인 경우
            if (!isRemainPositionsExist()) { // 더이상 둘 바둑돌이 없다면?
                this.answer = 1; // 정상적인 게임인 경우
            }

            // 이미 빙고상태이므로 더이상 진행하지 않아도 됨.
            // 더 둬야 할 바둑돌이 있는 경우 -> 정상적인 게임 아닌 경우 : 어짜피 this.answer 가 0 으로 초기화되어있기 때문에 따로 값 넣어줄 필요 없음
            return;
        }

        if (!isRemainPositionsExist()) { // 현재 턴에 더이상 둘 바둑돌이 없는 경우
            this.answer = 1; // 게임의 승자는 없지만, 정상적으로 게임이 종료될 수 있다. -> 정상적인 게임 처리
            return;
        }

        // 참고 : 이 블럭은 선공(O) 은 아예 없고 후공(X) 만 있는 경우에 대한 예외처리. -> 이 부분은 dfs 밖으로 빼도 될듯 함
        if (!positionsMap.containsKey(symbol)) { // 현재 턴 (선공 or 후공) 이 둘 바둑돌이 아예 없는 경우
            if (!isRemainPositionsExist()) { // 현재 턴에 둘 바둑돌이 없으니까 더이상 게임이 진행될 수 없어야 하는데, 더 둘 수 있는 바둑돌이 있는지 확인
                this.answer = 1; // 없으면 정상적인 게임 처리
            }
            return; 
        }
        
        List<Position> positions = positionsMap.get(symbol); // 현재 턴의 좌표 리스트를 받음

        for (int i = 0; i < positions.size(); i++) {
            Position cur = positions.get(i); // cur : 현재 좌표
            if (cur.visit) { // 이미 사용한 돌이면 넘어감
                continue;
            }

            // 사용할 수 있는 좌표이면
            
            // curBoard 에 표시 하고
            curBoard[cur.i][cur.j] = symbol; 
            cur.visit = true;
            
            // 다음 dfs 로 넘어감
            dfs(symbol == FIRST_SYMBOL ? SECOND_SYMBOL : FIRST_SYMBOL, curBoard);
            
            // dfs 에서 빠져나오면 cur 표시했던거 다시 지움
            curBoard[cur.i][cur.j] = EMPTY_SYMBOL;
            cur.visit = false;
        }

    }

    // 빙고 여부
    private boolean isBingo(char[][] curBoard) {
        return isBingo(curBoard, FIRST_SYMBOL) || isBingo(curBoard, SECOND_SYMBOL);
    }

    private boolean isBingo(char[][] curBoard, char symbol) {
        return (curBoard[0][0] == symbol && curBoard[0][1] == symbol && curBoard[0][2] == symbol) ||
            (curBoard[1][0] == symbol && curBoard[1][1] == symbol && curBoard[1][2] == symbol) ||
            (curBoard[2][0] == symbol && curBoard[2][1] == symbol && curBoard[2][2] == symbol) ||
            (curBoard[0][0] == symbol && curBoard[1][0] == symbol && curBoard[2][0] == symbol) ||
            (curBoard[0][1] == symbol && curBoard[1][1] == symbol && curBoard[2][1] == symbol) ||
            (curBoard[0][2] == symbol && curBoard[1][2] == symbol && curBoard[2][2] == symbol) ||
            (curBoard[0][0] == symbol && curBoard[1][1] == symbol && curBoard[2][2] == symbol) ||
            (curBoard[2][0] == symbol && curBoard[1][1] == symbol && curBoard[0][2] == symbol);
    }

    // 아직 놔야 할 바둑돌이 있는지 확인
    private boolean isRemainPositionsExist() {
        boolean result = false;

        for (char symbol : positionsMap.keySet()) {
            result |= positionsMap.get(symbol).stream()
                .filter(position -> !position.visit)
                .count() > 0;
        }

        return result;
    }

    private class Position {
        int i, j;
        boolean visit = false; // 방문 여부

        Position(int i, int j) {
            this.i = i;
            this.j = j;
        }
    }
}

DFS 완탐 시도시에도 성공한다.

---

💚 시간 복잡도 (경우의 수)

이중 for문 도는 부분이 가장 많은 시간을 잡아먹을 거 같은데, board의 길이와 board[i]의 길이 모두 3으로 고정된 상태라서 3X3 = 9다.. 그 외에 for문으로 순회하면서 빙고 확인하는 부분도 모두 for문 1번씩만 돌아서 시간 내 동작하는 것은 무리가 없다.

💚 회고

경우의 수를 쪼개서 엣지 케이스를 예외없이 고려하여 생각을 정리하고 구현하는 과정이 생각보다 어려운 것 같다. 꼼꼼히 예외를 따지지 않는다면 이런 류의 문제들은 예제에서는 통과해도 최종 통과가 안되는 경우가 많아서 실제 코테에서도 중요한 문제라고 볼 수 있기 때문이다. 더 열심히 하자.