[백준] 틱택토(7682)

문제 링크 : [백준] 틱택토(7682)

문제 설명

3*3 문자열 배열이 주어졌을 때, 틱택토 게임 규칙대로 경기가 진행되어 게임이 종료되었을 때 나올 수 있는 결과인지 판단하시오.

입력

한줄에 9개의 문자가 주어집니다.(각 문자의 내용은 아래와 같습니다.)
X : 먼저 두는 사람의 말
O : 나중에 두는 사람의 말
. : 빈 칸
입력은 반복되어 나타나며, end가 주어지면 종료됩니다.

XXXOO.XXX  
XOXOXOXOX  
OXOXOXOXO  
XXOOOXXOX  
XO.OX...X  
.XXX.XOOO  
X.OO..X..  
OOXXXOOXO  
end

출력

유효한 판인지 출력합니다.

invalid  
valid  
invalid  
valid  
valid  
invalid  
invalid  
invalid  

카테고리

#구현

시간 복잡도 상한

의미없음

해결 방법

1. 단순 구현으로 유효한 경우에 대한 경우의 수를 잘 정리하여야 합니다.

• 처음 놓는 사람(A)가 이긴 경우, X가 O보다 한칸 더 많아야 합니다.
• 나중에 놓는 사람(B)가 이긴 경우, O와 X의 수는 항상 같아야 합니다.
• 비긴 경우(이긴 사람이 없는 경우), X는 5개, O는 4개여야 합니다.(꽉 찬 경우)
• 예외의 경우로, A, B 둘 다 이긴 경우, 어떤 상황에서도 나올 수 없는 상황입니다.

2. 위의 상황을 구현합니다.

시간복잡도

의미없음

코드

#include<cstdio>
int i,j,x,y,n,m,z;
char s[10];
int c(int i,char m){
    if((s[i*3]==m&&s[i*3+1]==m&&s[i*3+2]==m)
    ||(s[i]==m&&s[i+3]==m&&s[i+6]==m)
    ||(s[0]==m&&s[4]==m&&s[8]==m)
    ||(s[2]==m&&s[4]==m&&s[6]==m))return 1;
    return 0;
}
int main(){
    while(1){
        z=x=y=n=m=0;
        scanf("%s",s);
        if(s[0]=='e')break;
        for(i=0;i<3;i++){
            x+=c(i,'O');
            y+=c(i,'X');
            for(j=0;j<3;j++){
                if(s[i*3+j]=='O')n++;
                if(s[i*3+j]=='X')m++;
            }
        }
        if(x&&y)z=0;
        else if(m-n==1&&y)z=1;
        else if(m==n&&x)z=1;
        else if(m==5&&n==4&&!x&&!y)z=1;
        printf("%svalid\n",z?"":"in");
    }
}