이상한 체스 - python

import copy

dx = [-1,0,1,0]
dy = [0,1,0,-1]

def can_move(posX,posY):
    if posX < 0 or posX >= n or posY < 0 or posY >= m or boards[posX][posY] == 6:
        return False
    return True
def fill_visit(visit,posX,posY,dir):
    while can_move(posX,posY):
        visit[posX][posY] = 1
        posX = posX + dx[dir]
        posY = posY + dy[dir]

def count_one(visit):
    tAnswer = 0
    for i in range(n):
        for j in range(m):
            if visit[i][j] == 0:
                tAnswer +=1
    return tAnswer

def fill(checks):
    visit = copy.deepcopy(boards)
    for check in checks: #check = [x,y,type,dir]
        x,y,type,dir = check
        if (type==1 and dir==0) or (type==2 and dir==1) or (type==3 and dir == 0) or (type==3 and dir==3) or (type==4 and dir == 0) or (type==4 and dir==1) or (type==4 and dir==3) or (type==5):
            fill_visit(visit,x,y,0)
        if (type==1 and dir==1) or (type==2 and dir==0) or (type==3 and dir==0) or(type==3 and dir==1) or (type==4 and dir==0) or(type==4 and dir==1)or (type==4 and dir==2) or type==5:
            fill_visit(visit, x, y, 1)
        if (type==1 and dir==2) or (type==2 and dir==1) or (type==3 and dir==1) or (type==3 and dir==2) or (type==4 and dir==1)or (type==4 and dir==2)or (type==4 and dir==3) or type==5:
            fill_visit(visit,x,y,2)
        if (type==1 and dir==3) or (type==2 and dir==0) or (type==3 and dir==2) or (type==3 and dir==3) or (type==4 and dir==0)or (type==4 and dir==2)or (type==4 and dir==3) or type==5:
            fill_visit(visit,x,y,3)
    oneCount = count_one(visit)
    global answer
    answer = min(oneCount,answer)

def check_recursive():
    def generate(start,checks):
        if len(checks) == len(horses):
            fill(checks)
            return
        for i in range(start,len(horses)):
            horseX = horses[i][0]
            horseY = horses[i][1]
            horseType = horses[i][2]
            if horseType == 1 or horseType==3 or horseType==4:
                for j in range(4):
                    checks.append([horseX, horseY,horseType, j])
                    generate(i + 1, checks)
                    checks.pop()
            elif horseType == 2:
                for j in range(2):
                    checks.append([horseX, horseY,horseType, j])
                    generate(i + 1, checks)
                    checks.pop()
            else:
                checks.append([horseX, horseY, horseType, 0])
                generate(i + 1, checks)
                checks.pop()
    generate(0,[])
n,m = map(int,input().split())
boards = []
answer = 100
for _ in range(n):
    boards.append(list(map(int,input().split())))

horses = [] # [x,y,type]

for i in range(n):
    for j in range(m):
        if boards[i][j] >= 1 and boards[i][j] <= 5:
            horses.append([i,j,boards[i][j]])


check_recursive()
print(answer)

생각할 점

1. 각 경우를 구하는 방법 : dfs로 하던 bfs로 하던 모든 종류를 구하기만 하면 될듯? 조합을 이용한 dfs로 했음 난

2. 구한 경우에 대해 값 구하기. 기존 board 복사해서 상황별로 채워넣고 복사한 board 돌면서 0 체크

 

시간복잡도 딱히 상관 없나...