def checkWin(play):
play_num = players[play]
for x in range(3):
if arr[x][0] == arr[x][1] == arr[x][2] == play_num:
return 2
for y in range(3):
if arr[0][y] == arr[1][y] == arr[2][y] == play_num:
return 2
if arr[0][0] == arr[1][1] == arr[2][2] == play_num:
return 2
if arr[0][2] == arr[1][1] == arr[2][0] == play_num:
return 2
return 0
def dfs(rc,play):
global result
if checkWin((play+1)%2)>1:
return -1
if rc <remain_cnt:
check_result = 10
for idx in range(remain_cnt):
if not visited[idx]:
visited[idx] = True
x,y = remain_list[idx]
arr[x][y] = players[play]
check_result = min(check_result,dfs(rc+1,(play+1)%2))
visited[idx] = False
arr[x][y] = 0
if check_result == 10 or check_result == 0:
return 0
else:
return -check_result
return 0
arr = []
# 1 = X
# 2 = O
# 착수하는 사람 부터
cnt_1 = 0
cnt_2 = 0
remain_cnt = 0
remain_list = []
players = [1,2]
for x in range(3):
temp = list(map(int,input().split()))
for y in range(3):
if temp[y] == 1:
cnt_1 += 1
elif temp[y] == 2:
cnt_2 += 1
else:
remain_cnt += 1
remain_list.append((x,y))
arr.append(temp)
visited = [False for _ in range(remain_cnt)]
start = 0
if cnt_1 > cnt_2:
start = 1
result = dfs(0,start)
answer = ['D','W','L']
print(answer[result])이 문제는 어려웠던 문제였다. 이 문제는 각각 최선의 수로 둔다는 것은 해당 수를 두고 다음턴에, 지지 않기를 바라는 상황이다.
그래서 상대턴이 시작할때, 이전턴에 뒀던 플레이어의 승리여부를 체크하고 체크를 한뒤에는 음수를 보내준다.
왜냐하면 서로 승패는 반대로 되기 때문이다. 그리고 승부가 나지 않았을 시에는 0을 반환하도록 한다.
def check():
for x in range(3):
prev_num = arr[x][0]
if not prev_num:continue
for y in range(1,3):
if prev_num != arr[x][y]:
break
else:
return prev_num
for y in range(3):
prev_num = arr[0][y]
if not prev_num: continue
for x in range(1,3):
if prev_num != arr[x][y]:
break
else:
return prev_num
prev_num = arr[0][0]
if prev_num:
for k in range(1,3):
if prev_num != arr[k][k]:
break
else:
return prev_num
prev_num = arr[0][2]
if prev_num:
for k in range(1,3):
if prev_num != arr[k][2-k]:
break
else:
return prev_num
return 0
def dfs(rc,player):
check_num = check()
if check_num != 0:
return check_num
if rc == 0: return -1
response = []
for x in range(3):
for y in range(3):
if arr[x][y]:continue
arr[x][y] = player
response.append(dfs(rc-1,3-player))
arr[x][y] = 0
if player in response:return player
if -1 not in response: return (3-player)
return -1
arr = [list(map(int,input().split())) for _ in range(3)]
cnt_1 = 0
cnt_2 = 0
player = 1
r_cnt = 0
for x in range(3):
for y in range(3):
if arr[x][y] == 1:
cnt_1 += 1
elif arr[x][y] == 2:
cnt_2 += 1
else:
r_cnt += 1
if cnt_1 > cnt_2:
player = 2
result = dfs(r_cnt,player)
if result == -1:
print('D')
elif result == player:
print('W')
else:
print('L')이 풀이가 좀 더 직관적일 수 있다.
모든 결과들을 저장한뒤에 해당 결과 내에서, 해당 플레이어의 번호가 있으면 승리한 것이므로, 해당 플레이어 번호를 보내주고,
무승부인 -1이 없으면 상대방이 이긴거기 때문에 상대방의 플레이어 번호를 return 해준다.
그리고 둘다 아닌경우에는 무승부이므로 -1을 반환해준다.
이 문제는 최선의 수가 무엇인지, 어떻게 승패를 판단하는지 어려웠던 문제였다.
'알고리즘 > 백준' 카테고리의 다른 글
| [BOJ/백준] 16724 피리 부는 사나이 (0) | 2021.07.15 |
|---|---|
| [BOJ/백준] 17951 흩날리는 시험지 속에서 내 평점이 느껴진거야 (0) | 2021.07.12 |
| [BOJ/백준] 16437 양 구출 작전 (0) | 2021.07.12 |
| [BOJ/백준] 13711 LCS 4 (0) | 2021.07.12 |
| [BOJ/백준] 13397 구간 나누기 2 (0) | 2021.07.12 |
