1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| def get_next_positions(board, loc): # 현재 위치(loc)에서 다음으로 이동 가능한 위치를 반환한다.
dRow, dCol = [0, 0, 1, -1], [1, -1, 0, 0]
next_positions = []
for d in range(4):
nr, nc = loc[0] + dRow[d], loc[1] + dCol[d]
if nr < 0 or nc < 0 or nr >= len(board) or nc >= len(board[0]):
continue
elif board[nr][nc] == 0:
continue
next_positions.append((nr, nc))
return next_positions
def search(board, aloc, bloc, turn): # dfs
if turn % 2 == 0:
next_positions = get_next_positions(board, aloc)
else:
next_positions = get_next_positions(board, bloc)
if not next_positions: # 현재 turn의 캐릭터가 이동할 수 없는 경우로 현재 turn의 캐릭터가 패배한다.
return turn % 2 != 0, turn # ((A가 이긴다면 True, B가 이긴다면 False), 현재까지 이동한 횟수)
if aloc == bloc: # 현재 캐릭터가 이동할 수 있으면서 aloc == bloc이면 현재 turn의 캐릭터가 승리한다.
return turn % 2 == 0, turn + 1
win, lose = [], []
if turn % 2 == 0:
board[aloc[0]][aloc[1]] = 0 # 캐릭터가 이동하면 기존의 자리는 0으로 처리한다.
for nr, nc in next_positions:
is_a_win, cnt = search(board, [nr, nc], bloc, turn + 1)
if is_a_win:
win.append(cnt)
else:
lose.append(cnt)
board[aloc[0]][aloc[1]] = 1 # 백트래킹
else:
board[bloc[0]][bloc[1]] = 0
for nr, nc in next_positions:
is_a_win, cnt = search(board, aloc, [nr, nc], turn + 1)
if not is_a_win:
win.append(cnt)
else:
lose.append(cnt)
board[bloc[0]][bloc[1]] = 1
if win: # 승리하는 경우가 하나라도 있으면
return turn % 2 == 0, min(win) # 승리하는 사람과 가장 빨리 승리하는 경우를 반환한다.
else: # 승리하는 경우가 하나도 없으면
return turn % 2 != 0, max(lose) # 패배하는 가장 긴 루트를 반환한다.
def solution(board, aloc, bloc):
winner, answer = search(board, aloc, bloc, 0)
return answer
|
