[백준] 1014. 컨닝 (Python / 파이썬)

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

1014번: 컨닝

 

---

1. 문제 풀이

 

본 문제는 컨닝2 문제와 동일하다. 그러나, 컨닝에는 알고리즘 분류에 "비트마스킹"이 있었기 때문에, 비트마스킹으로 풀어보았다.

 

만약 "...X..X"와 같이 입력이 주어졌다고 가정하자. 각각의 "."와 "X"를 하나의 비트라고 가정했을 때, 총 7개의 bit가 존재하기 때문에 가능한 경우의 수는 128가지며, 비트연산자를 활용하여 부분집합을 구하는 방식으로 쉽게 모든 경우의 수를 구할 수 있다.

 

1.1. "X"를 고려했을 때의 경우

그러나 이는, "X"를 고려하지 않은 판단이다. 즉, 앞서 구한 경우의 수에서 "X"에 학생을 배치한 경우의 수를 빼주어야 한다.

"X"를 1로 매핑한다면 "...X..X"는 "0001001"과 같이 표현할 수 있다. 만약, 어떤 숫자와 "0001001"에 대해 AND 연산을 수행했을 때, 0이 나오지 않는다면 이는 "X" 에 학생을 배치한 경우라고 할 수 있다.

즉, 첫 번째 경우처럼 학생을 배치할 수는 없으며, 두 번째는 학생을 배치할 수 있다. 

 

1.2. 인접한 경우

그러나, 첫 번째 경우처럼 학생을 배치한다면 컨닝을 할 수 있기 때문에, 인접의 경우까지 고려한다면 해당 조합 역시 틀린 조합이다. 따라서, 인접한 경우를 판별할 수 있는 함수를 따로 적용해주었다.

 

인접의 최소 단위는 두 학생이다. 따라서 두 학생이 인접했을 때를 비트로 표현하면 11(2)와 같이 표현할 수 있다. 11(2)를 왼쪽으로 shift해가면서 어떤 수와 AND 연산을 수행했을 때, 값이 그대로 나온다면 해당 수는 인접하는 학생을 가지고 있다고 생각할 수 있다.

 

즉, 어떤 row가 주어졌을 때, 다음과 같은 과정을 통해 가능한 배치 조합을 확인할 수 있다.

1. "."을 0, "x"를 1로 매핑하여 새로운 수를 구한다 (ex. "...x..x" => 0001001(2) => 9)
2. row의 모든 index에 대하여, 앞서 구한 숫자와의 AND 연산을 실행한다.
    2.1. 연산 결과가 0이면, X 위치에 학생을 배치하지 않은 것이므로 3으로 넘어간다.
    2.2. 연산 결과가 0이 아니면, X 위치에 학생을 배치한 것이므로 다음 index로 넘어가 2번 작업을 실행한다.
3. 11(2)를 계속해서 왼쪽으로 shift하면서, 인접 여부를 확인한다.
    3.1. index & (3 << offset) == (3 << offset)인 경우, 인접한 경우므로 다음 index로 넘어가 2번 작업을 실행한다.
    3.2. index & (3 << offset) != (3 << offset)인 경우, 인접하지 않은 경우기에 이는 가능한 경우이다.

이 두 과정을 통해, 하나의 row가 주어졌을 때, (1) 부숴진 좌석과 (2) 컨닝 여부를 고려한 모든 학생 배치의 조합을 구할 수 있다. 그러나, 대각선 앞이나 대각선 뒤에 앉아있을 때 컨닝이 가능하기 때문에, 이 역시 고려해주어야 한다.

1.3. 앞줄을 고려한 경우

만약 앞줄에 학생들이 "1010"과 같이 앉아 있다고 가정하자.

그리고 뒷줄에 "0101"과 "1010"과 같이 앉을 수 있다고 가정하자.

 

"1010"과 "0101"의 OR 연산 결과는 "1111"이다. 여기에 앞서 인접한 경우를 검증한다면 통과하지 못하기 때문에, 해당 경우처럼 앉는 것은 불가능하다.

 

"1010"과 "1010"의 OR 연산 결과는 "1010"이다. 여기에 앞서 인접한 경우를 검증한다면 통과하기에 해당 경우처럼 앉는 것은 가능하다.

 

즉, 앞줄에 앉아있는 경우와 뒷 줄에 앉아 있는 경우에 OR 연산을 수행한 후 인접한 경우를 고려했을 때 통과한다면 해당 경우처럼 앉을 수 있는 것이다.

2. 코드

import sys
# sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

num_tc = int(input()) # 테스트 케이스의 개수

def get_possible_seat(row):
    """
    앉을 수 있는 부분을 0, 앉을 수 없는 부분을 1로 표현
    """

    cur_num = 0
    
    for char in row:
        cur_num <<= 1

        if char == "x":
            cur_num |= 1

    return cur_num

def get_ones(number):
    """
    1의 개수 반환
    """
    std = 1
    answer = 0

    while std <= number:
        if std & number == std:
            answer += 1

        std <<= 1

    return answer

def adj_checker(number):
    """
    인접한지 여부 검증
    """
    std = 3

    while std <= number:
        if std & number == std:
            return True
        
        std <<= 1
        
    return False

for _ in range(num_tc):

    num_rows, num_cols = map(int, input().split()) # 세로, 가로 길이

    dp = [[0] * ((1<<num_cols)) for _ in range(num_rows)]
    mat = [input().rstrip() for _ in range(num_rows)]

    prev_possible_seat = 0

    for row_idx in range(num_rows):
        possible_seat = get_possible_seat(mat[row_idx]) # 앉을 수 없는 곳은 1로 표시

        for col_idx in range(1 << num_cols):

            if not (col_idx & possible_seat) and not adj_checker(col_idx): # 해당 위치에 앉을 수 있다면
                cur_ones = get_ones(col_idx) # 현재 조합의 학생 수 계산

                if not row_idx: # 가장 처음 row라면
                    dp[0][col_idx] = cur_ones

                else: # 두번째 row부터

                    max_std = cur_ones

                    for prev_col_idx in range(1 << num_cols): # 이전 column에 대하여

                        if not (prev_col_idx & prev_possible_seat) : # 이전 위치가 유효하다면

                            new_seat = prev_col_idx | col_idx

                            if not adj_checker(new_seat):
                                temp_std = cur_ones + dp[row_idx-1][prev_col_idx]

                                if temp_std > max_std:
                                    max_std = temp_std

                    dp[row_idx][col_idx] = max_std

        prev_possible_seat = possible_seat

    # 결과 확인
    print(max(dp[-1]))

3. 결과

---