[백준 14712] 넴모넴모 (Easy) Python 솔루션

문제 링크 : https://www.acmicpc.net/problem/14712

 

N x M 격자 안에 네모를 배열하되, 2 X 2 정사각형 모양이 없도록 하는 경우의 수를 구하는 문제이다.

예를 들면 격자가 2 X 3 이라고 할 때 세어야하는 경우와 아닌 경우는 아래와 같다.

 

 

행의 개수 N, 열의 개수는 M으로 주어지고, 시간제한은 1초이다. (1 ≤ N, M ≤ 25, 1 ≤ N × M ≤ 25)

 

아무리 생각해도 모든 경우의 수를 만들어낸 후, 네모가 있는지 검사하는 것이 가장 확실하다는 생각이 들었는데, 이중 list를 사용하면 시간도 메모리도 초과할 것이 뻔했다. 게다가 이러면 네모 유무를 확인하는것도 어려웠다.

 

각 경우의 수를 검사하는 방식을 엄청나게 최적화 해야 최대 2 ^ 25 가지 경우의 수를 1초안에 체크할 수 있어서 고민하다가...

각 열을 이진수로 나타내고, 이진수 계산으로 네모가 있는지 검사하기로 했다. 이런 방식을 bitmasking이라고 한다.

 

변수 bitmap의 이미지

위와 같은 격자는 이제 아래와 같이 표현된다.

# 0은 빈칸, 1은 넴모가 있는 칸
bitmap = [ 0b001, 0b111 ]

row1, row2 = bitmap[0], bitmap[1]

# 두 row가 위아래로 1을 가지고 있는 경우를 잡아낸다.
has_nemo_1 = '11' in bin(row1 & row2) # string의 in 연산자를 이용한 방식
has_nemo_2 = (row1 & row2) & (row1 & row2) >> 1 # shift 연산자를 활용한 방식

 

네모 유무를 어떻게 계산할지 알아냈으니, 이진수를 활용해서 모든 경우의 수를 만들어내는 일만 남았다.

range 함수와 itertools.product를 활용했다.

# ex) ROWS = 2, COLS = 2 라고 할 때
from itertools import product

SIZE = ROWS * COLS
ALL_POSSIBLE_ROWS = range(int('1' * COLS, 2) + 1) # 00 ~ 11
for bitmap in product(ALL_POSSIBLE_ROWS, repeat = ROWS):
    print(bitmap)
    
# 이진수 형식 출력결과
(00, 00)
(00, 01)
(00, 10)
(00, 11)
(01, 00)
(01, 01)
(01, 10)
(01, 11)
(10, 00)
(10, 01)
(10, 10)
(10, 11)
(11, 00)
(11, 01)
(11, 10)
(11, 11)

 

이렇게 얻어낸 솔루션 코드는 아래와 같다.

from itertools import product

def bitmasking(ROWS, COLS):
    SIZE = ROWS * COLS
    ALL_POSSIBLE_ROWS = range(int('1' * COLS, 2) + 1)
    cnt = 2 ** SIZE
    nemo_check = dict()

    # 가능한 모든 경우의 수 생성
    for bitmap in product(ALL_POSSIBLE_ROWS, repeat = ROWS):
    	# 인접한 모든 row 비교
        for row in range(ROWS - 1):
            both_1 = bitmap[row] & bitmap[row + 1]
            has_nemo = both_1 & (both_1 >> 1)
            if has_nemo:
                cnt -= 1
                break
    return cnt

# 백준 입출력
N, M = map(int, input().split(' '))
print(bitmasking(N, M))

 

느리긴해도 정확한 로직을 갖고 있으므로 우선 여기서 테스트케이스를 뽑아냈다.

로직 개선하려다가 아예 답이 틀려버렸을 때 큰 도움이 된다.

N	M	answer
2	3	57
2	4	216
2	10	641520
2	12	9221121
3	5	22077
3	6	160697
3	7	1169792
3	8	8515337
4	5	587920
4	6	8191392
5	5	15701273

 

이제 시간을 줄이기 위한 몇가지 로직을 추가했다.

 

1. row 혹은 column 수가 2 미만이면 2 x 2 네모가 생길 수 없다.

2. dp로 두 열을 비교하는 연산의 중복을 줄이자

3. row와 column이 뒤집혀도 연산 결과는 같으며, 이때 실행시간에 영향을 끼치는건 이중 for문에 들어가는 rows의 수다.

 

이렇게 완성한 코드는 아래와 같다.

from itertools import product

def bitmasking(ROWS, COLS):
    # row 또는 column 수가 2 미만이면 2 x 2 네모가 생길 수 없다.
    if ROWS < 2 or COLS < 2:
        return 2 ** (ROWS * COLS)
    
    # 둘 중 작은 수를 ROWS로 삼는다. for loop 실행 횟수가 감소한다.
    if ROWS > COLS:
        COLS, ROWS = ROWS, COLS
    
    SIZE = ROWS * COLS
    ALL_POSSIBLE_ROWS = range(int('1' * COLS, 2) + 1)
    cnt = 2 ** SIZE
    nemo_check = dict()

    # 미리 네모가 생기는 조합을 계산해서 저장한다.
    for bitmap in product(ALL_POSSIBLE_ROWS, repeat = 2):
        both_1 = bitmap[0] & bitmap[1]
        nemo_check[both_1] = both_1 & (both_1 >> 1)

    # 가능한 모든 경우의 수 중 네모가 존재하는 경우를 뺀다.
    for bitmap in product(ALL_POSSIBLE_ROWS, repeat = ROWS):
        for row in range(ROWS - 1):
            if nemo_check[bitmap[row] & bitmap[row + 1]]:
                cnt -= 1
                break
    return cnt

# 백준 입출력
N, M = map(int, input().split(' '))
print(bitmasking(N, M))

 

 

nemo_check의 key도 원래 tuple을 쓰다가, 어차피 row가 달라도 and 연산의 결과가 같으면 네모 위치는 같으므로 아예 and 연산 결과를 키로 삼았다. (아래 코드 참고) 이 덕분에 불필요한 메모리가 줄었다.

row1, row2 = bitmap[0], bitmap[1]
both_1 = row1 & row2

# tuple을 key로...
nemo_check[(row1, row2)] = both_1 & (both_1 >> 1)

# 중간 연산 결과를 key로...
nemo_check[row1 & row2] = both_1 & (both_1 >> 1)

 

 

여기에 컴파일러까지 pypy3로 바꾸니 이제 시간초과 없이 통과!