SWEA 4613. 러시아 국기 같은 깃발 (Python)(D4)

흰색a줄, 파란색b줄, 빨간색c줄을 색칠하는데, a>=1, b>=1, c>=1, a+b+c=N 이어야 하며 색칠해야하는 값이 최소이어야 한다.
먼저, N개의 줄에 대해 각 줄의 W,B,R의 갯수를 구한다.
이후 백트래킹으로 2~N-1줄에 대해 B가 색칠될 줄의 경우의 수를 구한다.
이때,

• 첫번째줄은 무조건 흰색, 마지막줄은 무조건 빨간색이다.
• 파란색줄은 무조건 이어져야 한다.
• 파란색줄은 무조건 1줄이상 있어야 한다.
  파란색줄이 색칠될 경우의 수가 정해지면 해당경우에 색칠해야 하는 칸의 수를 구하며 최소값 갱신
  ex)
  WWWWWWWWWWWWWW
  WWRRWWBBBBBBWW
  WRRRWWWBWWWWRB
  WWBWBWWWBWRRRR
  WBWBBWWWBBWRRW
  WWWWWWWWWWWWWW
• 2번째줄만 파란색
  -> 1번째줄은 흰색, 3~N번째 줄은 빨간색
• 2~3번째줄만 파란색
  -> 1번째줄은 흰색, 4~N번째 줄은 빨간색
• 3~5줄만 파란색
  -> 1~2번째줄은 흰색, 4~N번째 줄은 빨간색

이런식으로 색칠해야 되는 칸의 최소값을 갱신!

res=[]
def calc(vi):
    global tmp
    tmp2=0
    types='w'
    for i in range(2,N):
        if types=='w' and vi[i]==0:
            tmp2+=(M-li[i][0])
        elif vi[i]==1:
            tmp2+=(M-li[i][1])
            types='b'
        else:
            tmp2+=(M-li[i][2])
    tmp=min(tmp2,tmp)
    
def go(idx,vi,count,stop=0):
    if idx==N:
        if count==0: #파란색줄이 없다면, 패스!
            return
        calc(vi)
        return
    # stop의 역할 : 파란색줄이 듬성듬성 생기지 않게 컨트롤
    if stop!=2:
        vi[idx]=1
        go(idx+1,vi,count+1,1)
    vi[idx]=0
    go(idx+1,vi,count,2 if stop==1 or stop==2 else 0) 
    
for m in range(int(input())):
    tmp=10**9
    N,M=map(int,input().split())
    li=[[0,0,0] for i in range(N+1)]
    for i in range(1,N+1):
        S=input()
        for j in S:
            if j=='W':
                li[i][0]+=1
            elif j=='B':
                li[i][1]+=1
            else:
                li[i][2]+=1
    
    go(2,[0]*(N+1),0)
    tmp+=(M-li[1][0])+(M-li[N][2]) # 첫줄과 마지막줄 색칠칸 계산
    res.append(tmp)
for i in range(len(res)):
    print("#%d %s"%(i+1,res[i]))