프로그래머스 | Level 2 | 혼자서 하는 틱택토

Programmers | Level 2 | 혼자서 하는 틱택토

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Simulation

󰧭 Description

틱택토는 두 사람이 하는 게임으로 처음에 3x3의 빈칸으로 이루어진 게임판에 선공이 "O", 후공이 "X"를 번갈아가면서 빈칸에 표시하는 게임입니다. 가로, 세로, 대각선으로 3개가 같은 표시가 만들어지면 같은 표시를 만든 사람이 승리하고 게임이 종료되며 9칸이 모두 차서 더 이상 표시를 할 수 없는 경우에는 무승부로 게임이 종료됩니다.

할 일이 없어 한가한 머쓱이는 두 사람이 하는 게임인 틱택토를 다음과 같이 혼자서 하려고 합니다.

• 혼자서 선공과 후공을 둘 다 맡는다.
• 틱택토 게임을 시작한 후 "O"와 "X"를 혼자서 번갈아 가면서 표시를 하면서 진행한다.

틱택토는 단순한 규칙으로 게임이 금방 끝나기에 머쓱이는 한 게임이 종료되면 다시 3x3 빈칸을 그린 뒤 다시 게임을 반복했습니다. 그렇게 틱택토 수 십 판을 했더니 머쓱이는 게임 도중에 다음과 같이 규칙을 어기는 실수를 했을 수도 있습니다.

• "O"를 표시할 차례인데 "X"를 표시하거나 반대로 "X"를 표시할 차례인데 "O"를 표시한다.
• 선공이나 후공이 승리해서 게임이 종료되었음에도 그 게임을 진행한다.

게임 도중 게임판을 본 어느 순간 머쓱이는 본인이 실수를 했는지 의문이 생겼습니다. 혼자서 틱택토를 했기에 게임하는 과정을 지켜본 사람이 없어 이를 알 수는 없습니다. 그러나 게임판만 봤을 때 실제로 틱택토 규칙을 지켜서 진행했을 때 나올 수 있는 상황인지는 판단할 수 있을 것 같고 문제가 없다면 게임을 이어서 하려고 합니다.

머쓱이가 혼자서 게임을 진행하다 의문이 생긴 틱택토 게임판의 정보를 담고 있는 문자열 배열 board가 매개변수로 주어질 때, 이 게임판이 규칙을 지켜서 틱택토를 진행했을 때 나올 수 있는 게임 상황이면 1을 아니라면 0을 return 하는 solution 함수를 작성해 주세요.

 Constraints

• board의 길이 = board[i]의 길이 = 3
  • board의 원소는 모두 "O", "X", "."으로만 이루어져 있습니다.
• board[i][j]는 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
  • "."은 빈칸을, "O"와 "X"는 해당 문자로 칸이 표시되어 있다는 의미입니다.

󰦕 Examples

board	result
["O.X", ".O.", "..X"]	1
["OOO", "...", "XXX"]	0
["...", ".X.", "..."]	0
["...", "...", "..."]	1

Solutions

󰘦 Code

import java.util.*;

class Solution {
    public int solution(String[] board) {
        String[][] grid = new String[board.length][board.length];  // 게임판을 2차원 배열로 변환
        int blacks = 0;  // "O"의 개수를 카운트
        int whites = 0;  // "X"의 개수를 카운트
        boolean blackWin = false;  // "O"가 승리했는지 여부
        boolean whiteWin = false;  // "X"가 승리했는지 여부
        
        // 2차원 배열로 게임판을 변환하고 각 플레이어의 기호 개수를 셈
        for (int i = 0; i < board.length; i++) {
            String[] row = board[i].split("");  // 각 행을 문자로 분리
            for (int j = 0; j < board.length; j++) {
                grid[i][j] = row[j];
                if (row[j].equals("O")) blacks++;  // "O"의 개수를 증가
                if (row[j].equals("X")) whites++;  // "X"의 개수를 증가
            }
        }
        
        // 각 플레이어가 승리했는지 여부를 판단
        blackWin = checkWinner(grid, "O");  // "O"의 승리 여부 확인
        whiteWin = checkWinner(grid, "X");  // "X"의 승리 여부 확인
        
        // 규칙 위반 여부를 확인
        if (blackWin && whiteWin) return 0;  // 둘 다 승리하면 규칙 위반
        if (blackWin && blacks != whites + 1) return 0;  // "O"가 승리했을 때 "O"는 "X"보다 1개 많아야 함
        if (whiteWin && blacks != whites) return 0;  // "X"가 승리했을 때 "O"와 "X"의 개수가 같아야 함
        if (blacks < whites || blacks > whites + 1) return 0;  // "O"는 "X"보다 1개 많거나 같아야 함
        
        return 1;  // 규칙을 모두 지켰다면 1 반환
    }
    
    // 승리 여부를 확인하는 함수
    private boolean checkWinner(String[][] grid, String player) {
        // 가로, 세로 방향으로 승리 여부 확인
        for (int i = 0; i < grid.length; i++) {
            int rows = 0;  // 가로 방향의 같은 기호 개수
            int cols = 0;  // 세로 방향의 같은 기호 개수
            for (int j = 0; j < grid.length; j++) {
                if (grid[i][j].equals(player)) rows++;  // 가로로 같은 기호를 찾음
                if (grid[j][i].equals(player)) cols++;  // 세로로 같은 기호를 찾음
            }
            if (rows == grid.length || cols == grid.length) return true;  // 가로 또는 세로로 승리했을 때 true 반환
        }
        
        // 대각선 방향으로 승리 여부 확인
        if (grid[0][0].equals(player) && grid[1][1].equals(player) && grid[2][2].equals(player)) return true;  // 왼쪽 위에서 오른쪽 아래로 대각선
        if (grid[2][0].equals(player) && grid[1][1].equals(player) && grid[0][2].equals(player)) return true;  // 왼쪽 아래에서 오른쪽 위로 대각선
        
        return false;  // 승리 조건을 만족하지 않으면 false 반환
    }
}

 Approaches

이 문제는 주어진 틱택토 게임판이 규칙을 지키며 진행된 게임 상황인지 여부를 판단하는 문제입니다. 게임 도중 규칙이 어겨졌다면 0을 반환하고, 규칙을 잘 지켰다면 1을 반환합니다. 이를 위해 각 플레이어의 말 수와 승리 조건을 확인하는 과정을 거칩니다.

1. 문제 분석

틱택토 게임에서 "O"는 선공, "X"는 후공입니다. 따라서 "O"의 개수는 "X"보다 하나 더 많거나, 동일해야 정상적인 게임 상황입니다. 이와 함께, 승리 조건도 확인해야 합니다. "O"와 "X"가 각각 가로, 세로, 또는 대각선으로 3개가 연속으로 있는지를 확인하고, 두 명이 동시에 승리할 수 없음을 보장해야 합니다. 게임판의 상태에 따라 승리 여부를 판단하고 규칙 위반 여부를 검토합니다.

2. 접근 방식

다음 단계로 문제를 해결합니다:

1. 게임판 상태 확인: 먼저, "O"와 "X"의 개수를 세어, 선공과 후공의 순서 규칙을 지켰는지 확인합니다. "O"는 "X"보다 하나 더 많거나, 같아야 합니다.
2. 승리 여부 판단: 각 플레이어가 승리했는지 확인합니다. 가로, 세로, 대각선 방향으로 같은 기호가 3개 있는지를 탐색합니다.
3. 규칙 위반 확인: 두 명이 동시에 승리했는지 여부, 승리한 후에도 게임이 계속되었는지 여부를 확인합니다. 이러한 경우 규칙 위반으로 간주하여 0을 반환합니다.

3. 게임판 상태 분석

틱택토의 기본 규칙을 바탕으로, 먼저 게임판을 2차원 배열로 변환하고 "O"와 "X"의 개수를 세어 규칙을 준수했는지 판단합니다. "O"의 개수는 "X"보다 1개 많거나 같아야 하며, 이를 위해 주어진 게임판을 순회하면서 각 기호의 개수를 확인하고 2차원 배열로 변환하여 이후 승리 여부를 쉽게 체크할 수 있도록 준비합니다.

String[][] grid = new String[board.length][board.length];  // 게임판을 2차원 배열로 변환
int blacks = 0;  // "O"의 개수
int whites = 0;  // "X"의 개수

for (int i = 0; i < board.length; i++) {
    String[] row = board[i].split("");
    for (int j = 0; j < board.length; j++) {
        grid[i][j] = row[j];
        if (row[j].equals("O")) blacks++;
        if (row[j].equals("X")) whites++;
    }
}

4. 승리 여부 판단

각 플레이어가 승리했는지를 판단하기 위해, 가로, 세로, 대각선 방향으로 동일한 기호가 3개 연속으로 있는지 확인합니다. 승리 조건을 만족하는 경우 해당 플레이어가 승리했음을 나타냅니다.

"O"와 "X"에 대해 각각의 승리 여부를 확인하기 위해, 동일한 로직을 반복하게 됩니다. 이를 방지하고 중복을 제거하기 위해, 승리 여부를 확인하는 검증 과정을 별도의 함수로 분리합니다. 이렇게 함으로써 "O"와 "X"에 대해 가로, 세로, 대각선에서 승리 조건을 동일하게 검증할 수 있습니다. 이 함수는 각 플레이어가 승리했는지 확인하고, 그 결과를 반환합니다.

public int solution(String[] board) {
    ...
    boolean blackWin = checkWinner(grid, "O");  // "O"의 승리 여부 확인
    boolean whiteWin = checkWinner(grid, "X");  // "X"의 승리 여부 확인
    ...
}

private boolean checkWinner(String[][] grid, String player) {
    for (int i = 0; i < grid.length; i++) {
        int rows = 0;
        int cols = 0;
        for (int j = 0; j < grid.length; j++) {
            if (grid[i][j].equals(player)) rows++;
            if (grid[j][i].equals(player)) cols++;
        }
        if (rows == grid.length || cols == grid.length) return true;
    }
    
    if (grid[0][0].equals(player) && grid[1][1].equals(player) && grid[2][2].equals(player)) return true;
    if (grid[2][0].equals(player) && grid[1][1].equals(player) && grid[0][2].equals(player)) return true;
    
    return false;
}

5. 규칙 위반 여부 확인

마지막으로, 다음과 같은 규칙 위반 여부를 확인합니다:

• 두 플레이어가 동시에 승리했는지.
• 승리한 후에도 게임이 계속되었는지.
• "O"와 "X"의 개수가 규칙에 맞지 않는지.

이 중 하나라도 위반되었다면, 규칙 위반으로 간주하고 0을 반환합니다.

if (blackWin && whiteWin) return 0;  // 둘 다 승리하면 규칙 위반
if (blackWin && blacks != whites + 1) return 0;  // "O"가 승리했을 때 개수 조건 확인
if (whiteWin && blacks != whites) return 0;  // "X"가 승리했을 때 개수 조건 확인
if (blacks < whites || blacks > whites + 1) return 0;  // 순서 규칙 위반

6. 규칙을 모두 통과한 후 최종 결과 반환

모든 검사를 통과한 경우, 주어진 게임판이 틱택토의 규칙을 지켜서 진행된 상황이라고 판단할 수 있습니다. 이때, 규칙을 위반하지 않았다면 최종적으로 1을 반환합니다.

// 규칙을 모두 지켰다면 1 반환
return 1;

󰄉 Complexity

• ⏳ TC: O(1)
• 💾 SC: O(1)

틱택토 게임판은 3x3 크기이므로, 모든 탐색과 검사는 상수 시간 내에 이루어집니다. 따라서 시간 복잡도는 O(1)이며, 별도의 추가 공간을 사용하지 않으므로 공간 복잡도도 O(1)입니다.