문제 설명
Tic-Tac-Toe는 2인용 게임으로, 첫 번째 플레이어는 3×3 보드에 번갈아 “O”를 표시하고 두 번째 플레이어는 “X”를 표시합니다.
가로, 세로, 대각선으로 3개의 동일한 표시를 하면 같은 표시를 한 플레이어가 이기고 게임이 종료됩니다.
9개의 사각형이 모두 채워지고 더 이상 표시할 수 없게 되면 게임은 무승부로 끝납니다.
할 일 없는 두 사람이 하는 게임인 tic-tac-toe를 혼자 할 거예요.
- 그는 전반전과 후반전을 모두 혼자서 관리했습니다.
- Tic-Tac-Toe 게임을 시작한 후 “O”와 “X”를 번갈아 표시하십시오.
Tic-Tac-Toe는 간단한 규칙으로 게임이 빨리 끝나면 게임이 끝난 후 3×3 공백을 치고 다시 게임을 반복합니다.
그러한 틱택토 게임을 수십 번 한 후, 수줍은 사람은 게임 중에 규칙을 어기는 다음과 같은 실수를 저질렀을 수 있습니다.
- “O”를 표시하고 “X”를 표시하거나 그 반대로 표시할 차례입니다.
“X”를 표시하고 “O”를 표시할 차례입니다. - 첫 번째 또는 두 번째 플레이어가 이기고 게임이 종료되더라도 게임은 계속됩니다.
게임 도중 어느 순간 게임판을 보며 자신이 실수를 한 것은 아닌가 하는 생각이 들었다.
혼자 틱택토를 했기 때문에 치는 과정을 본 사람이 없어 장담할 수 없다.
하지만 실제로 tic-tac-toe 룰을 지킨다면 일어날 수 있는 상황인지는 게임판만 봐도 판단할 수 있을 것 같고, 문제가 없다면 계속 게임을 해보도록 하겠습니다 .
혼자 게임중에 질의한 tic-tac-toe 게임판의 정보를 담고 있는 string array board를 파라미터로 주면, 이 게임판이 규칙에 따라 tic-tac-toe로 진행하면, 게임 상황이면 1을 반환합니다.
그렇지 않은 경우 0을 반환하는 해결 함수를 작성합니다.
제한
- 보드 길이 = 보드 길이(i) = 3
- 보드의 요소는 모두 “O”, “X” 및 “.”로 구성됩니다.
- 보드의 요소는 모두 “O”, “X” 및 “.”로 구성됩니다.
- 보드(i)(j). 나 + 1행 제이 + 열 1에 해당하는 셀의 상태를 표시합니다.
- ㅏ “.” 공백을 나타내고 “O” 및 “X”는 해당 문자로 공백을 나타냅니다.
- ㅏ “.” 공백을 나타내고 “O” 및 “X”는 해당 문자로 공백을 나타냅니다.
내 솔루션
사실 문제의 본질을 알 수 없으니 dfs를 이용해서 해결해야 할까요? 그럼 어떻게 해결해야 할까요? 나는 매우 걱정했다.
아직 잘 모르겠어서 생각나자마자 해결해봤습니다.
인간이라면 일단 주어진 board 정상인지 비정상인지 판단하는 방법에 대해 생각했습니다.
- 먼저 O와 X의 수를 세고 첫 번째 공과 두 번째 공이 교대로 놓여 있는지 확인합니다.
- 가로, 세로, 대각선 중 어느 하나에 O나 X와 같은 표시가 나오는지 확인했습니다.
1. 먼저 O와 X의 수를 세고 첫 번째와 두 번째 공이 교대로 놓여 있는지 확인합니다.
def solution(board):
o_count = 0
x_count = 0
for i in range(3):
for j in range(3):
if board(i)(j) == 'O':
o_count += 1
elif board(i)(j) == 'X':
x_count += 1
if x_count - o_count > 0 or o_count - x_count > 1:
return 0– 전체 검색 board사용된 O와 X의 수 count 했다.
그럼에도 불구하고 board크기가 3*3으로 매우 작기 때문에 전체 검색을 해도 괜찮을 것으로 판단되었습니다.
– O가 먼저 나오므로 O는 X보다 하나 크거나 O와 X의 수가 같아야 합니다.
따라서 OX는 1개 이상, X의 수는 O를 초과하지 않아야 합니다.
2. 가로, 세로, 사선 아래에 O 또는 X가 같은 표시를 하는지 확인하였다.
def checkFinished(board, now):
# 현재 위치 가로/세로 확인
for i in range(3):
i_cnt = 0 # 가로
j_cnt = 0 # 세로
for j in range(3):
if board(i)(j) == now:
i_cnt += 1
if board(j)(i) == now:
j_cnt += 1
if i_cnt == 3:
return True
if j_cnt == 3:
return True
# 대각선 확인
# 왼->오
cnt = 0
for i in range(3):
if board(i)(i) == now:
cnt += 1
if cnt == 3:
return True
# 오->왼 대각선
cnt = 0
for i in range(3):
if board(i)(2-i) == now:
cnt += 1
if cnt == 3:
return True
return False1. 이중 for 문 내부에 가로/세로로 끝나는 부분이 있는지 확인했습니다.
– 0번째, 1번째, 2번째 행의 너비를 확인하여 동일한 광고가 가로로 완성되었는지 확인했습니다.
– 계산하기로로와 같은 마킹이 완성되었는지 확인하기 위해 열 0, 1 및 2의 세로 방향이 확인되었습니다.
2. 왼쪽에서 오른쪽으로, 오른쪽에서 왼쪽으로 두 개의 대각선이 있습니다.
① 왼쪽에서 오른쪽으로 (0, 0) > (1, 1) > (2, 2)를 검색하면,
② (0, 3) > (1, 1) > (2, 0)을 검색하면 오른쪽에서 왼쪽 대각선이 완성되었는지 확인할 수 있습니다.
for를 통해 각 인덱스에 액세스하려면 for i in range(3) 각 라인에서만 가능합니다.
i 로 열다 2-i이렇게 하면 오른쪽 > 왼쪽 방향으로 대각선 셀에 접근할 수 있습니다.
checkFinished 함수 호출
if checkFinished(board, 'O'):
if o_count == x_count:
return 0
if checkFinished(board, 'X'):
if o_count > x_count:
return 0– solution 완성된 부분이 있는지 확인하기 위해 함수 내부의 함수를 호출하고 번호가 유효한지 확인했습니다.
– O가 이미 완료되었고 O와 X의 개수가 같으면 O가 완료되었음에도 불구하고 X가 표시되므로 False Case이므로 0이 반환됩니다.
– X가 완료되었으나 O의 개수가 X보다 많으면 X가 완료되었음에도 불구하고 O로 표시되어 false인 경우이다.
확실한 출처
def checkFinished(board, now):
# 현재 위치 가로/세로 확인
for i in range(3):
i_cnt = 0 # 가로
j_cnt = 0 # 세로
for j in range(3):
if board(i)(j) == now:
i_cnt += 1
if board(j)(i) == now:
j_cnt += 1
if i_cnt == 3:
return True
if j_cnt == 3:
return True
# 대각선 확인
# 왼->오
cnt = 0
for i in range(3):
if board(i)(i) == now:
cnt += 1
if cnt == 3:
return True
# 오->왼 대각선
cnt = 0
for i in range(3):
if board(i)(2-i) == now:
cnt += 1
if cnt == 3:
return True
return False
def solution(board):
o_count = 0
x_count = 0
for i in range(3):
for j in range(3):
if board(i)(j) == 'O':
o_count += 1
elif board(i)(j) == 'X':
x_count += 1
if x_count - o_count > 0 or o_count - x_count > 1:
return 0
if checkFinished(board, 'O'):
if o_count == x_count:
return 0
if checkFinished(board, 'X'):
if o_count > x_count:
return 0
return 1– 위와 같이 하면 성공합니다.
예이!
– 하지만 무작정 풀었다는 느낌을 지울 수 없다.
맞나요?!
더 좋은 방법이 있는 것 같습니다.
실패의 검토
맨 처음에 solution 기능
if x_count - o_count > 0 or o_count - x_count > 1:
return False이 부분
if o_count < x_count:
return False나는 이걸했다.
그러자 반례라도 있는 것처럼 테스트 케이스 9, 10, 37, 40, 44에서 실패가 발생했다.
– O가 X보다 크게 설정되는 경우는 고려하지 않았다.
암튼 해봤는데.. 좀 무식한 방법인지는 모르겠지만.. 새로운 문제라서 그런지 구글링을 해보니 다른 분들이 해결책을 못찾으셔서 저도 그렇게 생각했습니다.
풀려고 노력했지만 그래도 풀었다는게 자랑스럽네요…
언젠가 다른 분들의 해결법이 뜨면 그때 또 좋은 방법을 연구해서 해결해보겠습니다!
–
문제가 있으면 의견에 알려주십시오.