1014번-컨닝
문제 : https://www.acmicpc.net/problem/1014
문제 조건
- 왼쪽 위, 오른쪽 위, 왼쪽, 오른쪽에 사람이 있으면 안됌
- 'x'가 아닌 곳에서 앉을 수 있음
위 조건 2개에 맞춰 학생들을 앉혀보면 될거같다.
문제 풀이
- n * m board판에서 n,m<=10 이므로 전체 탐색을 통해 진행해봐도 될것같다. 따라서 dfs를 통해 전체탐색을 진행해보자
- 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
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))
사실 필자는 board[y][x]='o', board[y][x]='.' 방법을 이용하여 백트래킹 + dfs 방식으로 진행하였으나 계속해서 틀렸습니다가 나왔다. 결국 문제 질문에 있는 글을 보고 dp(비트)를 시도하였다. 이런 생각을 어떻게 하는지... 한수 제대로 배웠다.
Author And Source
이 문제에 관하여(1014번-컨닝), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@youngjun0627/1014번-컨닝저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)