프로그래머스, 혼자서 하는 틱택토(java)

문제 설명

머쓱이가 혼자서 틱택토를 하는데, 중간에 규칙을 어기는 실수를 했을지도 모른다. 때문에 보드가 주어졌을 때 해당 보드가 규칙에 맞게 나올 수 있는 결과이면 1을 아니면 0을 반환하라.

 

규칙

1. 'O'이 선공 'X'가 후공이다.

2. 어느 기호든 빙고가 먼저 나오면 무조건 게임이 끝나야 한다.

 

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

프로그래머스

문제 풀이

첫 번째 접근

솔직히 어려웠고 중간에는 개열받았다.

 

아무튼 처음에는 깊이 우선 탐색으로 모든 경우를 생각해보려고 했다. 그러니까 (0,0)에 'O'을 넣었을 때 가능한 모든 경우와 'X'를 넣었을 때 가능한 모든 경우를 말이다. 이 경우를 구한 다음 주어진 지도와 비교해보려고 했다. 그러나 안타깝게도 나의 뇌가 생각하는 중간에 자꾸만 길을 잃어서 이렇게 풀지는 못했다.

 

그러던 와중 무조건 안 되는 경우가 있다는 걸 알게 되었다.

'O'이 선공이므로 무조건 'O'의 수가 'X'의 수보다 같거나 커야 한다. 즉, 'X'의 수가 'O'보다 큰 경우는 절대적으로 틀린 경우이다. 또 하나 'O'이 'X'보다 커야 하지만 그 차이가 2이상이면 안 된다. 'O' 다음에는 무조건 'X'가 와야 하므로 둘을 뺐을 때 그 수가 0혹은 1이여야만 한다. 즉, 'O'의 수와 'X'의 수의 차가 2이상이면 그건 틀린 틱택토라는 의미다.

 

좋아... 이렇게는 됐고 이제 빙고가 되는 경우의 수를 구해주면 된다.

처음에는 방향 좌표 계산 수를 모두 구해 깊이 우선 탐색으로 풀어주려 했다. 그러나 주어진 좌표가 가질 수 있는 경우를 따지는 것이 너무 복잡해져서 이렇게 풀지 못했다. 내가 간과한 사실이 하나 있는데, 주어진 택택토 지도의 크기는 3x3이라 직접 그 경우의 수를 구해줘도 된다는 거다.

 

두 번째 풀이

우리가 만들 수 있는 빙고의 경우는 가로는 총 3개, 세로는 총 3개, 오른쪽 대각선 1개, 왼쪽 대각선 1개로 총 8개가 된다.

그렇다면 그냥 하나씩 구해주면 된다.

 

일단 가로와 세로는 중복되는 부분이 있으니 반복문을 이용해서 주어진 target과 같은지 확인한다. 그리고 대각선은 2개 뿐이니 직접 좌표를 넣어서 계산한다.

 

이렇게 만들 수 있는 총 빙고의 수를 'O'와 'X' 각각 구했다면 이제 이 둘을 비교할 차례이다.

 

일단 둘 다 빙고가 나와서는 안 된다. 어느 한 쪽에서 빙고가 나오면 무조건 게임 종료이니, 두 쪽에서 모두 빙고가 1개 이상 나왔다면 이는 잘못된 경우이다.

 

이제 'O'에서 빙고가 나온 경우를 생각해보자. 'O'에서 빙고가 나온 경우 'O'의 수가 'X'의 수보다 무조건 1개가 많아야 한다. 이는 'O'이 선공이기 때문이다. 즉, 'O'에서 빙고가 나왔다는 의미는 'X'보다 하나를 더 놓았다는 뜻으로 이를 위반할 시 잘못된 틱택토라고 할 수 있다.

 

다음으로 'X'에서 빙고가 나온 경우를 생각해보자. 이때는 무조건 'O'의 수가 'X'의 수보다 작아야 한다. 왜냐하면 'X'에서 빙고가 나왔다는 의미는 'O'을 하나 놓은 후 'X'를 놓아 빙고가 만들어졌다는 뜻이기 때문이다. 'X'를 놓아 빙고를 만들었는데, 'O'을 하나 더 놨다? 이건 규칙 위반이다.

 

참고

나는 처음에는 빙고의 수가 무조건 1보다 크면 잘못된 지도라고 생각했다. 왜냐하면 첫 빙고가 나오면 무조건 게임을 끝내야 하는데, 첫 빙고가 나오고 나서 또 다른 빙고가 나왔다고 해석했기 때문이다. 하지만, 이 생각은 틀렸는데 한 번에 두 개 이상의 빙고가 나올 수 있다.

 

예를 들어서 (1, 1)은 비어 있다고 생각하고 이를 관통하는 가로와 대각선에 값이 모두 체워져있다고 생각해보자. 이렇게 되면 (1, 1) 하나만 넣었을 뿐인데 빙고가 적어도 2개 이상은 생긴다.

 

그러므로 아래의 조건은 넣어줘서는 안 된다.

        if(zeroWinCount > 1 || xWinCount > 1){
            return 0;
        }

코드

java

import java.util.*;

class Solution {
    public static char[][] map;
    
    public int solution(String[] board) {
        int answer = 1;
        int zeroCount = 0;
        int xCount = 0;
        int zeroWinCount = 0;
        int xWinCount = 0;
        map = new char[3][3];
        
        for(int i=0; i<3; i++){
            for(int j=0; j<3; j++){
                map[i][j] = board[i].charAt(j);
                if(board[i].charAt(j) == 'O'){
                    zeroCount++;
                }else if(board[i].charAt(j) == 'X'){
                    xCount++;
                }
            }
        }
        
        if(xCount > zeroCount || zeroCount - xCount >= 2){
            return 0;
        }
        
        zeroWinCount = countWin('O');
        xWinCount = countWin('X');
        
        //둘다 빙고가 나오면 안 된다.
        if(zeroWinCount > 0 && xWinCount > 0){
            return 0;
        }
        
        /*
        문자 하나로 빙고가 2개 이상 나오는 경우가 있기 때문에 해당 조건을 넣어줘서는 안 된다.
        if(zeroWinCount > 1 || xWinCount > 1){
            return 0;
        }*/
        
        //O에서 빙고가 나오는 경우
        if(zeroWinCount > 0){
            //X의 수가 더 많으면 안 된다.
            if(zeroCount-xCount != 1){
                return 0;
            }
        }
        
        //X에서 빙고가 나오는 경우
        if(xWinCount > 0){
            if(zeroCount > xCount){
                return 0;
            }
        }
        
        

        return answer;
    }
        
    public int countWin(char target){
        int count = 0;
        
        for(int i=0; i<3; i++){
            if(map[i][0] == target && map[i][1] == target && map[i][2] == target){
                count++;
            }
            if(map[0][i] == target && map[1][i] == target && map[2][i] == target){
                count++;
            }
        }
        
        if(map[0][0] == target && map[1][1] == target && map[2][2] == target){
            count++;
        }
        
        if(map[0][2] == target && map[1][1] == target && map[2][0] == target){
            count++;
        }
        
        return count;
    }

}