틱택토
면접 대비시간 제한1초메모리 제한128 MB
3x3 틱택토 격자가 주어질 때, 합법적인 수 순서로 그 배치에 도달할 수 있는지 판정한다.
문제
틱택토(Tic Tac Toe)는 3×3 격자에서 하는 아이들의 놀이입니다. 먼저 플레이어 X가 비어 있는 칸 하나에 X를 놓습니다. 그다음 플레이어 O가 비어 있는 칸 하나에 O를 놓습니다. 이렇게 X와 O가 번갈아 두며, 격자가 모두 채워지거나 한 플레이어의 기호가 한 줄(가로, 세로, 대각선)을 완전히 차지할 때까지 계속합니다.
처음의 빈 격자는 점 9개로 나타냅니다. X 또는 O를 둘 때마다 해당 위치를 X나 O로 채웁니다. 아래 예시는 X가 이기는 한 판에서 게임의 시작부터 끝까지 각 격자 상태를 보여 줍니다.
... X.. X.O X.O X.O X.O X.O X.O
... ... ... ... .O. .O. OO. OO.
... ... ... ..X ..X X.X X.X XXX
주어진 격자가 올바른 틱택토 게임의 한 장면이 될 수 있는지 판별하세요. 즉, 게임의 시작과 끝 사이 어느 시점에 이 격자가 나타나도록 하는 수순이 존재하는지 판단하면 됩니다.
입력
첫째 줄에 테스트 케이스의 개수 이 주어집니다. 이어지는 개의 줄에 개의 격자가 빈 줄로 구분되어 주어집니다. 각 격자는 세 줄로 되어 있고, 한 줄은 .(빈 칸), X, O 중 하나인 문자 세 개로 이루어집니다.
출력
각 테스트 케이스마다 한 줄에 yes 또는 no를 출력합니다. 해당 격자가 올바른 틱택토 게임의 한 장면이 될 수 있으면 yes를, 그렇지 않으면 no를 출력합니다.