문제 : https://www.acmicpc.net/problem/1014

문제 조건

1. 왼쪽 위, 오른쪽 위, 왼쪽, 오른쪽에 사람이 있으면 안됌
2. 'x'가 아닌 곳에서 앉을 수 있음

위 조건 2개에 맞춰 학생들을 앉혀보면 될거같다.

문제 풀이

1. n * m board판에서 n,m<=10 이므로 전체 탐색을 통해 진행해봐도 될것같다. 따라서 dfs를 통해 전체탐색을 진행해보자
2. dp를 이용해서 최댓값을 유지하면 진행해야 될거같다.

자세히 풀이를 설명하자면 다음과 같다.
우선 n-queen 문제와 같이 행 단위로 쪼개서 dfs를 진행할 것이다. 이때 한 행에서 일어날 수 있는 모든 경우의 수를 조사해야된다. 한 행에 대한 경우의 수를 generate하는 함수는 다음과 같다.

def generate_row(y,x,cur,prev,rows):
    
    if x==m:
        rows.append(cur)
        return
    
    if check(x,cur,prev) and board[y][x]=='.':
        generate_row(y,x+1, cur|(1<<x), prev,rows)
    generate_row(y,x+1, cur, prev,rows)

재귀 함수를 통해 순열을 생성한다. 이때 문제 조건에 맞게 cur과 prev를 이용해서 check를 진행할 것이다. check 조건에 true를 반환한다면 학생이 앉을 수 있으므로 cur에 비트 마스킹을 해준다.

비트 마스킹이란?

check함수를 통해 설명을 해보도록 하겠다.

def check(x, cur, prev):
    cur|=(1<<x)
    if m==1: # m이 1일때 처리
        return True
    if x==0 and (prev&(1<<x+1) or cur&(1<<x+1)):
        return False
    if x==m-1 and (prev&(1<<x-1) or cur&(1<<x-1)):
        return False
    if x>0 and (prev&(1<<x-1) or cur&(1<<x-1)):
        return False
    if x<m-1 and (prev&(1<<x+1) or cur&(1<<x+1)):
        return False
    
    return True

비트 마스킹은 bit 연산을 통해 최적화된 연산을 할 수 있다. 예를 들어 100 & 110 이라면 100으로 출력된다. 즉, 각 자리에 맞게 and연산을 취해서 위같은 예시에서는 첫번째만 둘다 1이고, 두번째 세번째 자리는 0을 포함하므로 0이다. 이를 이용해서 m=10이고 첫번째와 세번째 자리에 학생이 있다면 다음과 같이 표현할 수 있다.
1010000000
만약 여기에서 5번째 자리에 학생을 앉힌다면
1010100000
만약 여기에서 6번째 자리에 학생을 앉힌다면
1010110000
근데, 문제조건에서 양옆에 학생이 앉으면 안되므로 이는 위 코드에서 네번 째 if문에 걸린다(cur&(1<<x-1)).

위처럼 비트 연산을 통해 check처리를 해주면 보다 빠르게 연산을 할 수 있다(visit 느낌)

dfs

위에서 한 행에 대하여 모든 경우를 생성해주고 해당 행에 앉아있는 학생의 수를 계산한다. 그리고 dp 최댓값을 유지하며 dfs를 해주면 끝!!

전체 코드

import copy

C = int(input())

def check(x, cur, prev):
    cur|=(1<<x)
    if m==1:
        return True
    if x==0 and (prev&(1<<x+1) or cur&(1<<x+1)):
        return False
    if x==m-1 and (prev&(1<<x-1) or cur&(1<<x-1)):
        return False
    if x>0 and (prev&(1<<x-1) or cur&(1<<x-1)):
        return False
    if x<m-1 and (prev&(1<<x+1) or cur&(1<<x+1)):
        return False
    
    return True



def dfs(y,state):
    global rows, dp
    if y==n:
        return 0
    if dp[y][state]!=-1:
        return dp[y][state]
    
    dp[y][state]=0
    rows = []
    generate_row(y,0,0,state, rows)
    
    for cur in rows:
        cnt = 0
        for i in range(m):
            if cur&(1<<i):
                cnt+=1
        
        dp[y][state] = max(dp[y][state], cnt+dfs(y+1,cur))
    
    return dp[y][state]

def generate_row(y,x,cur,prev,rows):
    
    if x==m:
        rows.append(cur)
        return
    
    if check(x,cur,prev) and board[y][x]=='.':
        generate_row(y,x+1, cur|(1<<x), prev,rows)
    generate_row(y,x+1, cur, prev,rows)
        
    
        
        
for _ in range(C):
    
    n,m = map(int,input().split())
    board = []
    for _ in range(n):
        board.append(list(input()))
    
    '''
    n,m = 10, 10
    board = [list('....x.....'),
list('..........'),
list('..........'),
list('..x.......'),
list('..........'),
list('x...x.x...'),
list('.........x'),
list('...x......'),
list('........x.'),
list('.x...x....')]
    '''
    '''
    n,m = 3,5
    board = [list('..x..'),
            list('..x..'),
            list('.xxx.')]
    '''
    rows=[]
    dp = [[-1] * (1<<m) for _ in range(n)]
    print(dfs(0,0))

result

사실 필자는 board[y][x]='o', board[y][x]='.' 방법을 이용하여 백트래킹 + dfs 방식으로 진행하였으나 계속해서 틀렸습니다가 나왔다. 결국 문제 질문에 있는 글을 보고 dp(비트)를 시도하였다. 이런 생각을 어떻게 하는지... 한수 제대로 배웠다.