이번 문제는 백트레킹을 통해 해결하였다. 매번 대각선과 가로 세로를 확인하여 이전 차례의 상대의 글자가 일자로 배열해 있는지 확인한다. 그리고 여기서 나오는 결과를 통해 -1, 0, 1 중 하나를 반환하도록 한다. 수가 클 수록 좋은 경우로 배치하였기 때문에 -1, 0, 1은 L, D, W 순으로 매칭된다.

Code

grid = [list(map(int, input().split())) for _ in range(3)]
x, o = 0, 0
blanks = []
me = 0
for i in range(3):
    for j in range(3):
        if grid[i][j] == 1:
            x += 1
        if grid[i][j] == 2:
            o += 1
        if grid[i][j] == 0:
            blanks.append((i, j))
if x == o:
    me = 1
else:
    me = 2
def chk(turn):
    if turn == 1:
        before = 2
    else:
        before = 1
    if (grid[0][0] == grid[1][1] == grid[2][2] == before) or (grid[0][2] == grid[1][1] == grid[2][0] == before):
        return True
    for i in range(3):
        if (grid[i][0] == grid[i][1] == grid[i][2] == before) or (grid[0][i] == grid[1][i] == grid[2][i] == before):
            return True
    return False
def tic_tac_toe(cur):
    if cur == 1:
        nxt = 2
    else:
        nxt = 1
    mn = 2
    if chk(cur):
        return -1
    for i in range(3):
        for j in range(3):
            if grid[i][j] == 0:
                grid[i][j] = cur
                mn = min(mn, tic_tac_toe(nxt))
                grid[i][j] = 0
    if mn == 1:
        return -1
    elif mn == 2 or mn == 0:
        return 0
    else:
        return 1
if not blanks:
    print('D')
else:
    answer = tic_tac_toe(me)
    if answer == 1:
        print('W')
    elif answer == 0:
        print('D')
    else:
        print('L')