#7682번 틱택토 (C++)

링크 : www.acmicpc.net/problem/7682

7682번: 틱택토

문제 풀이는 다음과 같다. 

 

1. O가 X보다 많은 경우 

2. O나 X를 연이어 두는 경우

3. YES빙고가 많거나, NO빙고가 많거나, YES빙고와 NO빙고가 같은 경우

    3-(1) 각각의 경우에서 발생할 수 있는 invalid 조건을 서술한다

 

이 모든 경우 중 하나라도 해당되면 invalid가 나오고, 그렇지 않으면 valid가 나온다.

 

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

char arr[3][3];
string ttt;
int yesbing=0,nobing=0,temp=0,yes=0,no=0;
bool ans = false;

void check(){
   int cir=0, sci = 0;
   for(int i=0; i<3; i++){ // row
      for(int j=0; j<3; j++){
         if(arr[i][j]=='O') cir++;
         else if(arr[i][j]=='X') sci++;
      }
      if(cir==3) yesbing++;
      else if(sci==3) nobing++;
      cir=0, sci = 0;
   }
   for(int i=0; i<3; i++){ // col
      for(int j=0; j<3; j++){
         if(arr[j][i]=='O') cir++;
         else if(arr[j][i]=='X') sci++;
      }
      if(cir==3) yesbing++;
      else if(sci==3) nobing++;
      cir=0, sci = 0;
   }
   if(arr[0][0]=='O'&&arr[1][1]=='O'&&arr[2][2]=='O') yesbing++; // dia
   else if(arr[0][2]=='O'&&arr[1][1]=='O'&&arr[2][0]=='O') yesbing++;
   else if(arr[0][0]=='X'&&arr[1][1]=='X'&&arr[2][2]=='X') nobing++;
   else if(arr[0][2]=='X'&&arr[1][1]=='X'&&arr[2][0]=='X') nobing++;
}

int main(void) {
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   
   while(cin >> ttt){
      yesbing=0,nobing=0,temp=0,yes=0,no=0,ans=false;
      if(ttt=="end") break;
      for(int i=0; i<3; i++){
         for(int j=0; j<3; j++){
            arr[i][j] = ttt[temp++];
            if(arr[i][j]=='O') yes++;
            else if(arr[i][j]=='X') no++;
         }
      }
      check();
      if(yes>no) ans = true;
      else if(abs(yes-no)>1) ans = true; 
      else if(yesbing>nobing){
         if(yes<no) ans = true;
      }
      else if(yesbing<nobing){
         if(yes==no) ans = true;
      }
      else if(yesbing==nobing){
         int sum = yes+no;
         if(yesbing==1) ans = true;
         else if(yesbing==0&&sum<9) ans = true; 
      }
      if(ans) cout << "invalid" << "\n";
      else cout << "valid" << "\n";
   }
   return 0;
}

 

오답을 굉장히 많이 겪었는데, 희안하게도 100%정도 도달했을 때 쯤 틀렸다는 문구가 나왔다. 

혹시 100%가 나올쯤 틀린 경우가 나온다면, 아래 두 케이스를 천천히 분석해보길 권장한다. 

 

test1 : XOXOXOXO. (invalid)

test2 : XOXOXOX.. (valid)

 

백트래킹으로 분류되지만 백트래킹이 안되는 경우를 하나하나 찾아서 나열하는 기묘한 문제이다.

노가다를 봤을때는 단순 구현에 가깝고, 어쩌면 브루트포스와도 같은 문제였다.