[백준 7682 🥇] 틱택토

문제

틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 두 번째 사람이 O를 놓는다. 어느 때든지 한 사람의 말이 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하면 게임은 즉시 끝난다. 게임판이 가득 차도 게임은 끝난다.

게임판의 상태가 주어지면, 그 상태가 틱택토 게임에서 발생할 수 있는 최종 상태인지를 판별하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입력의 마지막에는 문자열 "end"가 주어진다.

출력

각 테스트 케이스마다 한 줄에 정답을 출력한다. 가능할 경우 "valid", 불가능할 경우 "invalid"를 출력한다.

문제풀이

import sys


# 최종 상태가 가능한 경우
# 1) X의 개수 = 5, O의 개수 =4 이면서 게임판이 모두 차있음(단, X,0 모두 3칸을 채운 상태가 아님)
# 2) X의 개수 = O의 개수이면서 O가 3칸을 이은 경우
# 3) X의 개수 = O의 개수+1 이면서 X가 3칸을 이은 경우
# X가 쌍대각선을 이루는 경우를 제외하고, 한 줄만 만족해야 함.

def success(tictactoe, xoro):
    # 대각선 만족하는 라인 개수
    dia_line=0
    # 평행선 만족하는 라인 개수
    pal_line=0
    # 3줄을 만족하는 경우 찾기
    # 1줄 이상 만족히면 불가능한 경우이기 때문에 line 변수에 만족하는 줄의 개수를 저장함.
    # 대각선으로 만족하는 경우
    if tictactoe[0][0]==xoro and tictactoe[1][1]==xoro and tictactoe[2][2]==xoro:
        dia_line+=1
    if tictactoe[0][2]==xoro and tictactoe[1][1]==xoro and tictactoe[2][0]==xoro:
        dia_line+=1
    for i in range(3):
        if tictactoe[i][0]==xoro and tictactoe[i][1]==xoro and tictactoe[i][2]==xoro:
            pal_line+=1
        if tictactoe[0][i]==xoro and tictactoe[1][i]==xoro and tictactoe[2][i]==xoro:
            pal_line+=1
    # 1줄만 만족하는 경우
    if dia_line+pal_line==1:
        return True
    elif dia_line==2:
        return True
    else:
        return False



while True:
    tictactoe=sys.stdin.readline().strip()
    if tictactoe=='end':
        sys.exit(0)
    tictactoe2d=[list(tictactoe[:3]),list(tictactoe[3:6]),list(tictactoe[6:])]
    # X의 개수
    numX=tictactoe.count('X')
    # O의 개수
    numY=tictactoe.count('O')
    # X의 개수 = O의 개수 +1 인 경우
    if numX==numY+1:
        # 꽉 채워져 있는데 누구도 이기지 못하고 종료되는 경우
        if numX==5 and numY==4 and not success(tictactoe2d,'X') and not success(tictactoe2d, 'O'):
            print('valid')
        # X가 이기는 경우(한 줄만 만족하면서 'O'는 한줄도 만족하면 안됨)
        elif success(tictactoe2d,'X') and not success(tictactoe2d, 'O'):
            print('valid')
        # 두 경우 모두 아니면 최종 상태에 도달할 수 있는 상태가 아님
        else:
            print('invalid')
    elif numX==numY:
        # O가 이기는 경우
        if success(tictactoe2d,'O') and not success(tictactoe2d,'X'):
            print('valid')
        else:
            print('invalid')
    else:
        print('invalid')

규칙을 찾아서 구현하는 문제였다. 처음에 생각하지 못했던 반례가 있어서 틀렸다가 질문 게시판을 보고 알았다!

 

처음에 생각했던 최종 상태가 될 수 있는 규칙은

1. 모두 꽉 채워져서 최종 상태까지 온 경우 : X가 5개, O가 4개이면서 X,O 모두 한 줄을 채우지 못한 상태
2. O로 이긴 경우 : X와 O의 개수가 동일하고 O가 한 줄을 채운 경우
3. X로 이긴 경우 : X의 개수가 O의 개수보다 한 개 더 많고 X가 한 줄을 채운 경우

구현을 쉽게 하려고 입력받은 게임판 tictactoe 문자열을 2차원 배열로 변경해서 tictactoe2d 배열에 저장했다.

그리고 numX에 X의 개수를 저장하고, numY에 O의 개수를 저장했다.

(변수명을 numO로 했어야 했는데 X가 나오다보니 무의식적으로 numY로 설정했다🙃..)

 

이후 차례로 위에서 생각했던 규칙에 만족하는지 확인한다. 

 

numX=numY+1인 경우는 위에서 예상했던 규칙 1번과 3번을 만족할 가능성이 있다. 

먼저 numX=5이고, numY=4인 경우엔 게임판이 꽉 채워진 상태인데 X, O 모두 한 줄을 만들지 못하는지 success 함수로 확인했다.

(success 함수 코드 설명은 밑에 있다)

 

그리고 X가 이기는 경우인지 확인했는데, 이 경우엔 X는 한 줄만 만족하면서 O는 한 줄도 만족해서는 안된다.

여기서 X가 한 줄만 만족하는지 확인하는 것 뿐만 아니라 O가 한 줄도 만족하지 못하는지 확인하는 것도 중요하다.

왜냐하면 O가 한 줄을 만드는지 확인하지 않으면 아래와 같은 경우는 필터링하지 못하기 때문이다. 

O	X	X
O	O	O
X	X	X

다음으로 numX==numY+1을 만족하지만 위 두 가지 경우가 아닌 경우는 최종 상태가 아니므로 invalid를 출력한다.

 

다음으로, numX==numY인 경우는 O가 이기는 경우인지 확인하기 위해서 O가 한 줄을 만들면서 X가 한 줄을 만들지 못하는지 확인해야 한다. 

예를 들어 아래의 경우, X가 먼저 한 줄을 채우고 게임이 끝나기 때문에 O가 다음 한 줄을 채울 수 없다. 

X	O	.
X	O	.
X	O	.

그런데 단순히 success(tictactoe2d, 'O')를 통해서 O가 한 줄을 채우는지만 확인하는 코드를 제출하고 통과를 받았었는데 다시 생각해보니 위의 경우는 불가능하지만 valid한 경우라고 출력하는데도 불구하고 통과가 됐다. 그래서 질문 게시판에 위 케이스에 대해서 질문을 남겨둔 상태이다!

답변이 달리거나 이유를 찾으면 이 글에 업데이트 하겠습니다

이제 success 함수에 대해서 코드 설명을 해보자면 다음과 같다.

def success(tictactoe, xoro):
    # 대각선 만족하는 라인 개수
    dia_line=0
    # 평행선 만족하는 라인 개수
    pal_line=0
    # 3줄을 만족하는 경우 찾기
    # 1줄 이상 만족히면 불가능한 경우이기 때문에 line 변수에 만족하는 줄의 개수를 저장함.
    # 대각선으로 만족하는 경우
    if tictactoe[0][0]==xoro and tictactoe[1][1]==xoro and tictactoe[2][2]==xoro:
        dia_line+=1
    if tictactoe[0][2]==xoro and tictactoe[1][1]==xoro and tictactoe[2][0]==xoro:
        dia_line+=1
    for i in range(3):
        if tictactoe[i][0]==xoro and tictactoe[i][1]==xoro and tictactoe[i][2]==xoro:
            pal_line+=1
        if tictactoe[0][i]==xoro and tictactoe[1][i]==xoro and tictactoe[2][i]==xoro:
            pal_line+=1
    # 1줄만 만족하는 경우
    if dia_line+pal_line==1:
        return True
    elif dia_line==2:
        return True
    else:
        return False

먼저 대각선을 만족하는 경우 dia_line에 +1을 한다. 

그리고 for문을 돌면서 행 또는 열을 기준으로 만족하는지 pal_line에 +1을 한다.

이렇게 만족하는 줄의 수를 모두 구한 다음에, dia_line과 pal_line을 더해서 1줄만 만족하는지 확인하고, 1줄만 만족한다면 True를 리턴한다.

그리고 dia_line의 2줄일 때도 True를 리턴해야 한다.

이 부분이 앞서 언급했던 생각하지 못했던 반례이다!

X	O	X
O	X	O
X	O	X

이 경우는 X가 대각선 한 줄을 채우면 종료되기 때문에 불가능한 경우라고 생각했는데, 가장 먼저 X를 둘 때, 가운데 부분에 두고 시작하면 가능한 케이스였다.

이 외에 만족하는 줄이 여러 줄이거나 없는 경우엔 False를 리턴한다.