틱택토 게임(tic tac toe)에서 가능한 모든 경우의 수를 찾는 방법
1. 틱택토 게임
3*3 게임판에서 O와 X를 서로 번갈아 둔다.
가로나 세로, 대각선으로 1줄(3개)이 서로 같게 만들면 승리
3*3 게임판에서 각각의 cell은 O, X, '.' 3가지중 한가지가 들어갈 수 있으므로..
모든 가능한 게임판의 경우는 $3^{9} = 19683$가지로 몇가지가 없다
이 경우 중간에 게임이 끝나서 더 이상 둘 수 없는 경우가 있기 때문에 그런 경우를 고려해서 제외하면 된다.
BFS를 이용해서 모든 가능한 경우를 조사할 수 있다.
1) deque에 (['.']*9, (첫 시작이 두는 수))를 먼저 넣고 BFS를 수행
특히 배열이 9칸이기 때문에 배열을 deepcopy해도 시간이 그렇게 오래걸리지 않는다.
2-1) 큐에서 하나씩 뽑은 다음, 게임판 배열을 순회해서 둘 수 있는 곳 '.'을 찾아 현재 턴의 사람이 둔다.
2-2) 둘 수 있는 곳이 없다면 게임이 무승부 난 것이다.
3) 수를 두고 게임의 승부가 결정났는지 조사한다.
4) 게임이 끝나지 않았으면 큐에 넣어주고 큐가 빌때까지 반복
2. 연습문제1
코딩테스트 연습 - 혼자서 하는 틱택토 | 프로그래머스 스쿨 (programmers.co.kr)
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
3. 풀이
주어진 게임판이 틱택토 규칙을 지켜서 두었을때 가능한 판인지 조사하는 문제
첫 시작이 O이므로 (['.']*9, O)부터 시작해서 BFS를 수행한다.
모든 경우를 조사하는 중에 주어진 게임판이 나올 수 있다면 True, 다 조사해도 나올 수 없다면 False
from collections import deque
#주어진 게임판과 현재 게임판이 서로 같은가?
def check(state,target):
for i in range(9):
if state[i] != target[i]:
return False
return True
def bfs(queue,target):
next_turn = {'O':'X', 'X':'O'}
while queue:
state,turn = queue.popleft()
f = check(state,target) #현재 게임판이 주어진 게임판과 일치하는지 검사
if f == True:
return 1
#게임판 9칸을 순회해서 둘 수 있는 곳 '.'을 찾는다
for i in range(9):
if state[i] == '.':
dstate = state[:] #배열을 deepcopy하고
dstate[i] = turn #현재 둘 수 있는 곳에 둔다음
f = end(dstate,i) #게임이 끝났는지 조사
if f == False:
queue.append((dstate,next_turn[turn])) #게임이 끝나지 않았다면 큐에 둔다
else:
#끝난 게임의 경우, 큐에 넣지 않고 주어진 게임판과 일치하는지 조사
g = check(dstate,target)
if g == True:
return 1
return 0
def solution(board):
queue = deque([(['.']*9,'O')]) #첫 시작이 O
target = ''.join(board)
return bfs(queue,target)
게임이 끝났는지를 체크하는 함수가 필요하다
현재 턴의 사람이 i번째를 두었다면.. 그러한 i번째를 중심으로 가로 세로 대각선을 확인해서
서로 같은 값이 한줄로 존재하는지 검사하면 된다
예를 들어 4번에 두었다면..
0,4,8
2,4,6
1,4,7
3,4,5
4줄을 검사해야한다
def end(state,i):
if i == 0:
if state[0] == state[1] and state[1] == state[2]:
return True
elif state[0] == state[3] and state[3] == state[6]:
return True
elif state[0] == state[4] and state[4] == state[8]:
return True
elif i == 1:
if state[0] == state[1] and state[1] == state[2]:
return True
elif state[1] == state[4] and state[4] == state[7]:
return True
elif i == 2:
if state[0] == state[1] and state[1] == state[2]:
return True
elif state[2] == state[5] and state[5] == state[8]:
return True
elif state[2] == state[4] and state[4] == state[6]:
return True
elif i == 3:
if state[3] == state[4] and state[4] == state[5]:
return True
elif state[0] == state[3] and state[3] == state[6]:
return True
elif i == 4:
if state[3] == state[4] and state[4] == state[5]:
return True
elif state[2] == state[4] and state[4] == state[6]:
return True
elif state[0] == state[4] and state[4] == state[8]:
return True
elif state[1] == state[4] and state[4] == state[7]:
return True
elif i == 5:
if state[3] == state[4] and state[4] == state[5]:
return True
elif state[2] == state[5] and state[5] == state[8]:
return True
elif i == 6:
if state[0] == state[3] and state[3] == state[6]:
return True
elif state[6] == state[7] and state[7] == state[8]:
return True
elif state[2] == state[4] and state[4] == state[6]:
return True
elif i == 7:
if state[6] == state[7] and state[7] == state[8]:
return True
elif state[1] == state[4] and state[4] == state[7]:
return True
elif i == 8:
if state[6] == state[7] and state[7] == state[8]:
return True
elif state[2] == state[5] and state[5] == state[8]:
return True
elif state[0] == state[4] and state[4] == state[8]:
return True
return False
4. 연습문제2
7682번: 틱택토
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄은 9개의 문자를 포함하며, 'X', 'O', '.' 중 하나이다. '.'은 빈칸을 의미하며, 9개의 문자는 게임판에서 제일 윗 줄 왼쪽부터의 순서이다. 입
www.acmicpc.net
5. 풀이
여러개의 테스트케이스가 주어지고, 각 테스트 케이스가 틱택토 게임의 최종상태인지를 검사하는 문제
애초에 틱택토 경우의 수가 몇가지 안되기 때문에
틱택토 모든 게임의 경우의 수를 먼저 조사한 다음 각 테스트 케이스마다 hash로 일치하는지를 검사하면 된다
9칸을 다 둬도 게임이 끝나지 않을 수 있다.
큐에서 하나 뽑고 뽑은 게임판을 순회할때 '.'이 존재하지 않는다면 더 이상 둘 수 있는 곳이 없고 무승부가 난 것
from collections import deque
from sys import stdin
#i번째 칸에 두었을때 게임이 끝났는가?
#i번째 칸을 중심으로 가로, 세로, 대각선 중 한줄(3개)이라도 같으면 게임 끝
def check(state,i):
#row
if i == 0 or i == 1 or i == 2:
if state[0] == state[1] and state[1] == state[2]:
return True
elif i == 3 or i == 4 or i == 5:
if state[3] == state[4] and state[4] == state[5]:
return True
else:
if state[6] == state[7] and state[7] == state[8]:
return True
#col
if i == 0 or i == 3 or i == 6:
if state[0] == state[3] and state[3] == state[6]:
return True
elif i == 1 or i == 4 or i == 7:
if state[1] == state[4] and state[4] == state[7]:
return True
else:
if state[2] == state[5] and state[5] == state[8]:
return True
#diag
if i == 0 or i == 8:
if state[0] == state[4] and state[4] == state[8]:
return True
elif i == 2 or i == 6:
if state[2] == state[4] and state[4] == state[6]:
return True
elif i == 4:
if state[0] == state[4] and state[4] == state[8]:
return True
elif state[2] == state[4] and state[4] == state[6]:
return True
return False
queue = deque([(['.']*9,'X')]) #첫 시작은 X
total = {} #X가 먼저 두었을 때 최종 게임판으로 가능한 것들
next_turn = {'X':'O', 'O':'X'}
while queue:
state,turn = queue.popleft()
find = False #현재 게임판에서 수를 둘 수 있는가?
for i in range(9): #게임판의 상태를 순회해서 둘 수 있는 곳 '.'을 찾는다
if state[i] == '.':
find = True
dstate = state[:]
dstate[i] = turn #현재 사람이 두고
f = check(dstate,i) #게임이 끝났는지 검사
if f == True:
total[''.join(dstate)] = 1 #게임이 끝났다면 최종상태가 된다
else:
queue.append((dstate,next_turn[turn])) #끝나지 않았다면 큐에 넣는다
if find == False: #더 이상 둘 수 있는 곳이 없어서 무승부난 경우
total[''.join(state)] = 1
while 1:
s = stdin.readline().rstrip()
if s == 'end':
break
if total.get(s,0) == 0:
print('invalid')
else:
print('valid')
다 조사하지 않아도 게임판만 보고도 최종 상태인지 판별할 수는 있다
물론 고려해야되는 조건이 매우 많다
X가 먼저 시작하기 때문에, 주어진 게임판은 X의 개수와 O의 개수가 서로 같거나 1개 더 많아야한다.
가로로 1줄만 서로 같거나, 세로로 1줄만 서로 같거나 대각선으로 1줄만 서로 같다(승부가 결정나는 경우)
서로 같은 줄이 없다면 X가 5개 O가 4개여야한다.
----------------------------------------------------------------------------------------------------------------------------------------------------
대각선으로 서로 같은 경우가 있는지 파악해본다.
대각선으로는 무조건 1줄만 가능하다.
이 때 조심할 점은 O가 이기는 경우와 X가 이기는 경우를 생각해보면
XOX
OXO
X
XOOX
X
X가 이기는 경우라면, X의 개수가 O의 개수보다 1개 더 많아야한다.
OX
XOX
O
O가 이기는 경우라면 O와 X의 개수가 서로 같아야한다
여기서 개수가 같은지 조사해야돼?? 이럴 수 있지만
OX
XO
O
이거는 대각선 한줄이 같은건 맞지만 O가 1개 더 많아서 불가능한 경우잖아
--------------------------------------------------------------------------------------------------------------------------------------------------------
가로줄이나 세로줄이 서로 같은지를 조사해본다.
여기서 조심할 점은 2줄 이상이 서로 같은 경우는 불가능하다고 생각할 수 있는데
가로줄이 1줄 서로 같고, 세로줄이 1줄 서로 같은 경우가 존재할 수도 있다는 점이다.
?X?
???
???
---------------
?X?
?O?
???
--------------
?XX
?OO
???
-------------
?XX
XOO
?O?
--------------
?XX
XOO
XOO
-------------
XXX
XOO
XOO
순서대로 둔다면 가로줄 1줄이 서로 같고 동시에 세로줄 1줄이 서로 같다.
하지만 O는 가로줄 1줄, 세로줄 1줄을 같게 만들수는 없다
?O?
?X?
???
---------
?OO
?XX
???
-----------
?OO
OXX
?X?
-------------
?OO
OXX
OXX
이 상태에서 둘 수있는 사람은 X이고,
XOO
OXX
OXX이므로 O는 두줄이 서로 같은 경우는 없다
-----------------------------------------------------------------------------------------------------------------------------------------
가로줄이나 세로줄 1줄이 서로 같은 경우는
XXX
OO
XO
XO
X
X가 서로 같은경우라면 X의 개수가 O보다 1개 더 많아야한다.
반대로
XXO
OOO
XX
O가 서로 같을려면 X와 O의 개수가 서로 같아야한다.
def check(s):
line = []
num = 0
a = 0 #X의 수
b = 0 #O의 수
c = 0 #.의 수
A = set()
for i in range(len(s)):
#판에서 X,O,'.'의 수를 센다
if s[i] == 'X':
a += 1
elif s[i] == 'O':
b += 1
else:
c += 1
A.add(s[i])
#0행, 1행, 2행 각각이 서로 같은지를 조사한다
if i % 3 == 2:
if len(A) == 1:
A =list(A)
if A[0] == 'X':
line.append(False)
num += 1
elif A[0] == 'O':
line.append(True)
num += 1
A = set()
#0열 1열 2열이 서로 같은지를 조사한다
A = set()
for i in range(3):
A.add(s[i])
A.add(s[i+3])
A.add(s[i+6])
if len(A) == 1:
A =list(A)
if A[0] == 'X':
line.append(False)
num += 1
elif A[0] == 'O':
line.append(True)
num += 1
A = set()
#대각선으로 서로 같은지를 조사한다
diag = 0
A = set()
A.add(s[0])
A.add(s[4])
A.add(s[8])
if len(A) == 1:
A =list(A)
if A[0] == 'X':
o = False
diag += 1
elif A[0] == 'O':
o = True
diag += 1
A = set()
A.add(s[2])
A.add(s[4])
A.add(s[6])
if len(A) == 1:
A =list(A)
if A[0] == 'X':
o = False
diag += 1
elif A[0] == 'O':
o = True
diag += 1
#대각선 한 줄이 서로 같은 경우
if diag == 1:
if o == True: #대각선 한줄이 O로 같다
if a == b: #O와 X의 개수가 서로 같아야한다
return True
else:
return False
else: #대각선 한줄이 X로 같다
if a == (b+1): #X의 개수가 O의 개수보다 1개 더 많다
return True
else:
return False
#가로줄,세로줄에 대한 검사
#두줄이 서로 같은 경우
if num == 2:
if len(set(line)) == 2: #XXX, OOO로 되는 경우는 불가능하다
return False
else: #XXX,XXX나 OOO,OOO로 서로 같은 경우
#XXX, XXX만 가능하다.
if line[0] == False and line[1] == False:
#XXX
#X??
#X??으로 하더라도, 게임이 결정될려면 개수도 맞아야한다.
#X가 5개이고 O가 0개이면 불가능한 경우니까
if a == 5 and b == 4:
return True
#가로줄이 1줄이 같거나 세로줄이 1줄로 서로 같은 경우
elif num == 1:
o = line[0]
if o == True: #OOO로 서로 같은 경우
if a == b: #O의 개수와 X의 개수가 서로 같아야한다
return True
else: #XXX로 서로 같은 경우
if a == (b + 1): #X의 개수가 O의 개수보다 1개 더 많다
return True
else: #승부가 결정나지 않는 경우, X의 개수가 5개, O의 개수가 4개여야한다.
if a == 5 and b == 4:
return True
return False'알고리즘 > 게임이론' 카테고리의 다른 글
| 게임이론 기본기 익히기1 - 약수 더하기 게임에서 반드시 이기는법 (0) | 2024.06.24 |
|---|---|
| 돌 무더기에서 팰린드롬(palindrome)인 정수 개수만큼 가져갈 때 이기는 방법 (0) | 2024.05.06 |
| 필승 전략 게임 - 베스킨라빈스 31 게임에서 반드시 이길 수 있을까? (0) | 2023.06.05 |
| 필승 전략 게임 - 돌 줍기 게임에서 반드시 이기는 방법 (0) | 2023.05.23 |
| 알고리즘 문제 해결(PS)을 위한 게임이론 기초지식 - 님 게임(Nim game) 배우기 (0) | 2023.05.15 |
