[C++] 백준/BOJ - 7682 : 틱택토

---

문제 이해 단계

https://www.acmicpc.net/problem/7682

7682번: 틱택토

3x3 게임판에 O와 X 두 가지를 가지고 게임을 한다.

무조건 X를 먼저 두는 것을 시작으로 X와 O를 번갈아가면서 둔다.

게임에서 이기는 조건은
X나 O가 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하는 것이다.
이를 틱택토라고 부르겠다.

틱택토를 성공하는 순간 게임은 즉시 끝난다.
게임판이 가득 차도 게임은 끝난다.

입력으로는 게임판의 최종상태가 주어지는데,
그 상태가 발생할 수 있는 상태인지 구하는 문제가능하면 valid, 불가능하면 invalid를 출력한다.

 

 

---

문제 접근 단계

https://kibbomi.tistory.com/183

boj, 백준) 7682. 틱택토 ( C / C++ )

해당 풀이는 이분 풀이를 많이 참고했습니다!! 감사합니다.

 

 

---

맵의 크기는 3x3으로 아주 작기 때문에  시간초과에 대해서는 크게 신경 안 써도 될 것 같다.

그래서 완전 탐색, 백트래킹 등등 원하는 방법은 모든 다 써도 될 것 같다.

문제에서 입력으로 주어지는 것은 최종 상태이기 때문에, 무조건 게임이 끝난 상태다.
이 말은 나올 수 있는 경우의 수가 3가지라는 뜻이다.

1. X가 이겼다.
2. O가 이겼다
3. 바둑판이 가득 찼다.

이 3가지 경우를 하나하나씩 분석해 보자.

 

X가 이긴 경우

x가 이겼다는 것은 당연히
x가 가로, 세로, 대각선 중 1개가 나타났다는 뜻이다.

이것 말고도 올바른 틱택토 게임이 되기 위해서 성립되어야 하는 조건이 있을까?

일단 이 게임은 틱택토가 완성되는 순간
게임이 종료되어 더 이상 말을 둘 수가 없다.

그렇기 때문에 X로 이루어진 틱택토가 하나만 존재해야 한다.

좀 더 풀어서 말하면,
X가 이긴 경우는 O로 이루어진 틱택토가 없어야 하며,
X로 이루어진 틱택토가 딱 하나여야 한다.

또한 X가 무조건 먼저 두기 시작하여 번갈아면서 두기 때문에,
게임이 끝나는 시점에선 무조건 X가 O보다 1개 더 많아야 한다.

정리해 보자면 다음과 같다.

1. X의 개수가 O보다 1개 더 많아야 한다.
2. O로 이루어진 틱택토가 없어야 한다.
3. X로 이루어진 틱택토가 하나여야 한다.

 

O가 이긴 경우

O가 이긴 경우도 X가 이긴 경우랑 똑같다. 다른 것은 딱 하나이다.

X가 먼저 시작했기 때문에 O가 틱택토를 이루는 시점에서는 
X와 O의 개수가 같아야 한다는 것이다.

정리해 보자면

1. X와 O의 개수가 같아야 한다.
2. X로 이루어진 틱택토가 없어야 한다.
3. O로 이루어진 틱택토가 하나여야 한다.

 

바둑판이 가득 찬 경우

마지막으로 가능한 경우는 바둑판이 가득 찬 경우이다.

이 경우는 딱 하나만 가능하다.

X부터 시작해서 번갈아가면서 가득 차서 종료되면
당연히 총 9칸이므로, X가 5개 O가 4개일 것이다.

그리고 9개를 가득 채우기 위해서는 중간에 종료되면 안 된다.
돌려 말하면 X나 O 중 틱택토가 하나도 발생하면 안 된다.

즉 정리하면,

1. X로 이루어진 틱택토가 없어야 한다.
2. O로 이루어진 틱택토가 없어야 한다.
3. X가 5개, O가 4개여야 한다.

이 경우를 제외한 나머지 경우는 모두 나올 수 없는 경우의 수라고 생각하면 된다.

이를 모두 조건을 걸어서 문제를 구현하면 된다.

 

 

---

문제 구현 단계

 

#include <iostream>
#include <string>
using namespace std;


// X가 이겼는지 확인
bool checkX(char map[3][3]){
    
    for(int i = 0; i < 3; i++){
        // 가로 체크
        if(map[i][0] == 'X' && map[i][0] == map[i][1] 
        && map[i][1] == map[i][2]) return true;

        // 세로 체크
        if(map[0][i] == 'X' && map[0][i] == map[1][i] 
        && map[1][i] == map[2][i]) return true;
    }
    // 대각 체크
    if(map[0][0] == 'X' && map[0][0] == map[1][1] 
    && map[1][1] == map[2][2]) return true;

    if(map[0][2] == 'X' && map[0][2] == map[1][1]
    && map[1][1] == map[2][0]) return true;

    return false;
}

// O가 이겼는지 확인
bool checkO(char map[3][3]){
    for(int i = 0; i < 3; i++){
        if(map[i][0] == 'O' && map[i][0] == map[i][1] 
        && map[i][1] == map[i][2]) return true;

        if(map[0][i] == 'O' && map[0][i] == map[1][i] 
        && map[1][i] == map[2][i]) return true;
    }
    if(map[0][0] == 'O' && map[0][0] == map[1][1] 
    && map[1][1] == map[2][2]) return true;

    if(map[0][2] == 'O' && map[0][2] == map[1][1]
    && map[1][1] == map[2][0]) return true;

    return false;
}
int main(){
    string input;
    while(true){
        char map[3][3];
        cin >> input;
        if(input[0] == 'e') break;

        // x와 o의 개수
        int x = 0;
        int o = 0;
        for(int i = 0; i < 9; i++) {
            // 3x3 2차원 배열로 만들기
            map[i/3][i%3] = input[i];
            if(input[i] == 'X') x++;
            else if(input[i] == 'O') o++;
        }
        bool isX = checkX(map);
        bool isO = checkO(map);

        if(isX && !isO && x == o+1) printf("valid\n"); // X가 이긴 경우
        else if(!isX && isO && x == o) printf("valid\n"); // O가 이긴 경우
        else if(!isX && !isO && x == 5 && o == 4) printf("valid\n"); // 가득 찬 경우
        else printf("invalid\n"); // 위 경우에 다 포함 안될때
    }
    return 0;
}

위에서 설명한 그대로 코드로 구현하였다.

모든 것은 주석으로 따로 설명해 놨기 때문에 크게 설명할 것은 없을 거라고 생각한다.
1차원 맵을 3x3으로 만들었다는 거 정도? 그것 외에는 딱히 없는 것 같다.

풀이는 여기까지고 글을 마치겠다.

 

 

---

시행착오

모든 경우의 수를 다 찾았다고 생각했는데도 결국엔 틀렸습니다가 떴다.
그냥 O랑 X랑 구분할걸, 괜히 같이 처리하려다가 복잡해졌다.

못 풀었다는 게 너무 슬프다.

생활비..

https://toss.me/howudong

howudong님에게 보내주세요