[SWEA 2112] 보호 필름

접근

약품을 투입할 수 있는 모든 조합을 확인했을 때 완전탐색으로 풀이가 가능하다고 생각하였다. 따라서 K가 2 이상일 때 약품을 투입하는 조합을 생성하여 해당 셀을 모두 0 또는 1로 바꾸어주었다. 그리고 모두 성능검사에 통과하는지 판단하는 함수로 전달하여 판단하였다. 

이 문제는 계속 49개만 맞았다고 나왔는데 문제점을 파악하기 어려웠다. 계속 시도를 해보다가 뒤늦게 깨달았는데 나의 풀이에 문제가 있었다. 만약 3개의 막에 약품을 주입한다했을 때 해당 막의 셀들을 모두 0 또는 1로 바꾸어주었다. 하지만 이렇게하면 3개의 막 중에 2곳은 0 1곳은 1을 주입할 수도 있는 경우의 수를 놓치고 있었다. 따라서 이 부분을 해결한 후에 PASS를 받을 수 있었다.

 

구현

- 성능 검사에 통과할 수 있는지 판단하는 함수이다.

def isPossible(board):
    for x in range(W):
        flag = board[0][x]
        count = 1
        for y in range(1, D):
            if flag == board[y][x]:
                count += 1
                if count >= K:
                    break
            else:
                flag = board[y][x]
                count = 1
        if count != K:
            return False
    return True

- 약품을 투입할 위치를 전달받아 해당 위치의 모든 셀들을 p로 변경하였고

- 투입하는 위치가 아닐 때는 본래의 셀들을 대입하였다.

- 최종적으로 새로운 2차원 리스트를 반환하였다.

def change(y_list, p, board):
    new_board = [[0 for _ in range(W)] for _ in range(D)]
    for y in range(D):
        if y in y_list:
            for x in range(W):
                new_board[y][x] = p
        else:
            for x in range(W):
                new_board[y][x] = board[y][x]

    return new_board

- 만약 K가 1이거나 약품을 주입하지 않아도 통과할 때는 answer에 0을 대입한다.

- 그렇지 않다면 약품을 투입하는 막의 위치의 조합을 구하여 해당 위치에 약품을 주입한다.

- 먼저 전달받은 조합에 모두 0을 주입하고 통과할 수 있는지 검사한다.

- 이후에는 위치를 1개씩 추가하여 1을 주입한다.

- 1을 주입할 때마다 통과할 수 있는지 검사한다.

    if K == 1 or isPossible(board):
        answer = 0
    else:
        for k in range(1, D+1):
            for combi in combinations(range(D), k):
                new_board = change(list(combi), 0, board)
                if isPossible(new_board):
                    answer = k
                    break
                y_list = []
                for c in combi:
                    y_list.append(c)
                    new_board = change(y_list, 1, new_board)
                    if isPossible(new_board):
                        answer = k
                        break
                if answer < D + 1:
                    break
            if answer < D + 1:
                break

---

전체 코드

from itertools import combinations
test_case = int(input())

def isPossible(board):
    for x in range(W):
        flag = board[0][x]
        count = 1
        for y in range(1, D):
            if flag == board[y][x]:
                count += 1
                if count >= K:
                    break
            else:
                flag = board[y][x]
                count = 1
        if count != K:
            return False
    return True

def change(y_list, p, board):
    new_board = [[0 for _ in range(W)] for _ in range(D)]
    for y in range(D):
        if y in y_list:
            for x in range(W):
                new_board[y][x] = p
        else:
            for x in range(W):
                new_board[y][x] = board[y][x]

    return new_board

def show(board):
    for y in range(D):
        for x in range(W):
            print(board[y][x], end=' ')
        print()
    print()
for tc in range(test_case):
    D, W, K = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(D)]

    answer = D + 1
    if K == 1 or isPossible(board):
        answer = 0
    else:
        for k in range(1, D+1):
            for combi in combinations(range(D), k):
                new_board = change(list(combi), 0, board)
                if isPossible(new_board):
                    answer = k
                    break
                y_list = []
                for c in combi:
                    y_list.append(c)
                    new_board = change(y_list, 1, new_board)
                    if isPossible(new_board):
                        answer = k
                        break
                if answer < D + 1:
                    break
            if answer < D + 1:
                break

    print("#{} {}".format(tc+1, answer))