백준 1014번: 컨닝 (Bitmask)

문제링크:1014번: 컨닝 (acmicpc.net)

1014번: 컨닝

이 문제는 교실의 상태가 최대 10*10 상태로 주어졌을때, 조건 내에 각 위치에 학생들을 최대로 앉힌 수를 구하는 문제이다. 조건은

1. 교실의 책상 N*M 칸중 책상이 부숴져 앉을 수 없는 칸이 있다.

2. 학생들은 컨닝을 할 수 있기에 학생들은 양 옆에 나란히 앉을 수 없고, 한칸 앞의 대각선 방향에 앉을 수 없다.

 

나는 각 행의 학생 상태를 비트마스킹으로 표현하고 0행부터 N-1행까지 DP로 최대 학생 수를 탐색하여 문제를 풀었다.

import sys

C=int(sys.stdin.readline().rstrip())

for _ in range(C):
    N,M=map(int,sys.stdin.readline().rstrip().split())
    board=[]
    
    for i in range(N): #교실 상태 비트로 표현
        row=list(sys.stdin.readline().rstrip())
        bitrow=[]
        for i in row:
            if i=='.':
                bitrow.append(1)
            else:
                bitrow.append(0)
        board.append(bitrow)

    dp=[[0 for i in range(1<<M)] for j in range(N)]

    visitbinary=[]
    for c in range(1<<M): #행에 학생 둘 나란히 있는 경우 제외한 모든 경우 visitbinary에 저장
        nocnt=0
        for j in range(M):
            if c&(1<<j):
                if 0<=j-1:
                    if c&(1<<(j-1)):
                        nocnt=1
                        break
                if j+1<M:
                    if c&(1<<(j+1)):
                        nocnt=1
                        break
        if nocnt==0:
            visitbinary.append(c)
    #dp[i][visit]=K ->i=행 까지 채운 경우 visit=학생상태 일때의 K=최대 학생 수
    for c in visitbinary: #DP위해 0행 채워주기
        nocnt=0
        cnt=0
        for j in range(M): #0~M-1열까지 돌아보며 학생이 있으면 cnt+=1
            if c&(1<<j):
                if board[0][j]==0: #학생이 책상 부순 곳에 있는 경우 제외
                    nocnt=1
                    break
                cnt+=1
        if nocnt==0:
            dp[0][c]=cnt

    for i in range(1,N): #DP로 다음 행 채워주기
        for prc in visitbinary: #prc는 추가되는 위행의 학생 상태 비트로 표현
            for nwc in visitbinary: #nwc는 추가되는 행의 학생 상태 비트로 표현
                nocnt=0
                cnt=0
                for j in range(M): #0~M-1열까지 돌아보며 학생이 있으면 cnt+=1
                    if nwc&(1<<j):
                        if board[i][j]==0:
                            nocnt=1
                            break
                        if 0<=j-1:
                            if prc&(1<<(j-1)): #이전 열의 대각선 방향에 학생이 놓인경우 제외
                                nocnt=1
                                break
                        if j+1<M:
                            if prc&(1<<(j+1)): #이전 열의 대각선 방향에 학생이 놓인경우 제외
                                nocnt=1
                                break
                        cnt+=1
                if nocnt==0:
                    dp[i][nwc]=max(dp[i][nwc],dp[i-1][prc]+cnt)

    print(max(dp[-1]))

먼저 교실 상태의 입력을 비트로 board에 저장했다.1은 앉을 수 있고 0은 앉을 수 없는 상태이다. 다음으로 한 행에 학생들이 있는 상태를 비트로 표현하였다. 한 행의 길이는 M이기에 최대 (1<<M) 만큼의 경우의 수가 있다. 이는 최악의 경우 2^10 (1024) 의 경우의 수이다. 하지만 학생들은 나란히 앉을 수 없다는 조건은 모든 행에서 성립하기에 두 학생이 나란히 앉은 경우가 하나라도 있는 상태를 제외시킨 visitbinary 리스트를 만들어 주었다. 학생이 있을 경우 1, 없을 경우 0으로 표현한다. 예시로 M이 10일때, 1111111111, 1100000000 과 같은 상태들은 나란히 앉은 학생이 있으므로 제외한다.

 

그렇다면 M이 10일때, visitbinary에는 1010101010, 1001001001 과 같은 상태들이 남는다. 앞으로 행을 탐색할 때에 (1<<M)의 모든 경우를 탐색하는 대신 visitbinary내 의 상태만 탐색하면 된다. 최악의 경우 len(visitbinary)로 길이를 찾아본 결과 144로 모든 경우인 1024보다 훨씬 적어진 것을 알 수 있다.

 

먼저 DP를 하기 위해 dp의 첫 행부터 학생 수를 채워 주었다. 아까 말했듯 visitbinary 내의 상태들을 이용해 주었다. 앞으로 매 행의 상태를 탐색할 때에는 visitbinary를 사용한다. 그리고 1열부터 N-1열까지 i행을 차례대로 채워 주었는데, 각 행을 채울 때 바로 위 행의 대각선 방향에 학생이 위치하면 안된다는 조건을 고려해주어야 한다. 바로 위 행의 학생 상태를 prc, 현재 행의 학생 상태를 nwc로 정하고 nwc의 학생이 있는 위치 열 (j)를 탐색해 나간다. 만약 board[i][j]==0 인 경우 앉을 수 없기에 제외시켜 주고 prc(바로 위 행)에 j-1, j+1 위치에 학생이 있다면 위 행의 대각선 방향에 학생이 위치하므로 제외시켜 준다. 위의 모든 조건에 제외되지 않은 경우, nwc의 상태로 cnt만큼의 학생 수를 새로 앉히는 것이 가능하다는 뜻이다.

 

가능한 경우 dp[i][nwc]를 dp[i-1][prc] + cnt 과 기존 값과 비교하여 큰 값으로 업데이트 해 주면 dp[-1]에는 마지막 열에서 각 상태 당 앉을 수 있는 최대 학생 수들이 저장된다.