[백준] 7682 틱택토 (C++)

작성일 In , Views: Disqus:

문제 링크 : https://www.acmicpc.net/problem/7682

풀이 및 구현

틱택토 보드판의 상태가 입력으로 들어오면 정상적으로 게임이 종료된 경우에는 valid를 출력하고 비정상적인 게임판이거나 아직 끝나지 않은 경우는 invalid를 출력해야 한다.

주의해야 할 점은 X가 선공이고 O가 후공이다.

valid한 경우는 세가지 경우가 있다.

  1. X의 승리
  2. O의 승리
  3. 빙고가 만들어지지 않고 더이상 말을 놓을 수 없는 무승부

그러면 각 경우에 대한 조건을 생각해보자.

먼저 X가 승리하기 위한 조건은 아래와 같다.

  • X가 선공이므로 X가 빙고를 완성하면 X의 개수가 O의 개수보다 1개 더 많아야 한다.
  • 이미 O가 빙고를 완성했으면 안된다.

같은 방식으로 O가 승리하기 위한 조건을 생각할 수 있다.

  • O가 후공이므로 O가 빙고를 완성하면 X의 개수와 O의 개수가 동일해야 한다.
  • 이미 X가 빙고를 완성했으면 안된다.

무승부인 경우는 아래와 같다.

  • 말을 놓을 수 있는 칸의 개수가 9개이므로 X와 O의 말의 개수의 합이 9개이어야 한다.
  • X가 선공이므로 X의 개수가 O의 개수보다 1개 더 많아야 한다.
  • X, O 모두 빙고가 없어야 한다.

위 내용을 기반으로 구현하면 된다.

우선 입력이 한줄로 들어오므로 이를 3 by 3으로 바꿔주었다.

1
2
3
4
vector<string> v(3);
for (int i = 0; i < 3; i++) {
    v[i] = s.substr(i * 3, 3);
}

그 다음 가로, 세로, 대각선을 확인해 빙고를 확인하면 해당 변수를 1로 설정했다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int O = 0, X = 0;

for (int i = 0; i < 3; i++) {

    // 가로줄
    if (v[i] == "XXX") X = 1;
    if (v[i] == "OOO") O = 1;
    
    // 세로줄
    if (v[0][i] == v[1][i] && v[1][i] == v[2][i]) {
        if (v[0][i] == 'X') X = 1;
        if (v[0][i] == 'O') O = 1;
    }
}
// \모양 대각선
if (v[0][0] == v[1][1] && v[1][1] == v[2][2]) {
    if (v[0][0] == 'X') X = 1;
    if (v[0][0] == 'O') O = 1;
}
// /모양 대각선
if (v[2][0] == v[1][1] && v[1][1] == v[0][2]) {
    if (v[2][0] == 'X') X = 1;
    if (v[2][0] == 'O') O = 1;
}

X와 O의 개수를 세고 위의 조건에 맞게 결과를 반환한다.

0을 반환하면 invalid, 1을 반환하면 valid이다.

위 세가지 조건을 만족하지 않으면 정상적으로 게임이 종료되는 경우가 아니므로 0을 반환한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
int x = count(s.begin(), s.end(), 'X'), o = count(s.begin(), s.end(), 'O');

// X가 승리
if (x == o + 1 && X && !O) return 1;

// O가 승리
if (x == o && !X && O) return 1;

// 무승부
if (x + o == 9 && x == o + 1 && !X && !O) return 1;

// 정상적으로 게임이 끝나지 않음
return 0;

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

int solve(string& s) {
    vector<string> v(3);
    for (int i = 0; i < 3; i++) {
        v[i] = s.substr(i * 3, 3);
    }

    int O = 0, X = 0;

    for (int i = 0; i < 3; i++) {
        if (v[i] == "XXX") X = 1;
        if (v[i] == "OOO") O = 1;
        if (v[0][i] == v[1][i] && v[1][i] == v[2][i]) {
            if (v[0][i] == 'X') X = 1;
            if (v[0][i] == 'O') O = 1;
        }
    }
    if (v[0][0] == v[1][1] && v[1][1] == v[2][2]) {
        if (v[0][0] == 'X') X = 1;
        if (v[0][0] == 'O') O = 1;
    }
    if (v[2][0] == v[1][1] && v[1][1] == v[0][2]) {
        if (v[2][0] == 'X') X = 1;
        if (v[2][0] == 'O') O = 1;
    }

    int x = count(s.begin(), s.end(), 'X'), o = count(s.begin(), s.end(), 'O');

    if (x == o + 1 && X && !O) return 1;
    if (x == o && !X && O) return 1;
    if (x + o == 9 && x == o + 1 && !X && !O) return 1;
    return 0;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    while (1) {
        string s; cin >> s;
        if (s == "end") break;
        if (solve(s)) cout << "valid\n";
        else cout << "invalid\n";
    }
}

후기

img.png

처음에 문제를 제대로 안읽어서 단순한 문제인줄 알았다.

그래서 가볍게 구현해서 예제를 돌려봤는데 완전 다르게 나와서 처음부터 다시 만들었다.