[알고리즘] 보호 필름

 

 

 

포인트

• 조합으로 줄을 선택하여서 약품을 바른다는 컨셉을 이해한다면 생각보다? 쉬운 내용일 수 도 있을 것 같습니다. 
• 또, 생각나는 내용은 연속된 숫자를 세는 방법인데 저는 함수 2개를 작성을 하여 열을 돌면서 열을 체크한다는 로직으로 작성을 하였습니다. 연속된 숫자가 있으면 수를 증가시키고 새로운 숫자가 나오면 값을 다시 업데이트 합니다. 후에 조건 값을 넘긴다면 True 를 반환하도록 작성하였습니다. 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

python

def check_column(col: int) -> bool:
	"""
	열을 확인한다. 같은 숫자가 나오면 +1 다른 것이 나오면 대체 후 1로 초기화
	:param col: 행의 위치
	:return: bool
	"""
	pointer1 = data[0][col]
	cnt = 1
	for i in range(1, d):
		if pointer1 == data[i][col]:
			cnt += 1
			if cnt >= k:
				# 합격 기준이 넘으면 통과
				return True
		else:
			pointer1 = data[i][col]
			cnt = 1
	return False


def check() -> bool:
	"""
	행을 결정하는 함수
	:return:bool
	"""
	for j in range(w):
		if not check_column(j):
			return False
	return True


def go(cnt: int, row: int) -> None:
	"""
	행을 지정하여 약을 치기 위한 함수
	:param cnt:
	:param row:
	:return:
	"""
	global answer
	
	if cnt >= answer:
		# 백 트랙킹
		return
	
	if check() or cnt == k:
		# 기준을 충족하면
		answer = min(answer, cnt)
		return
	else:
		for i in range(row, d):
			switched = []
			for j in range(w):
				if data[i][j] == 1:
					data[i][j] = 0
					switched.append(j)
			go(cnt + 1, i + 1)
			for j in switched:
				data[i][j] = 1
			
			switched = []
			for j in range(w):
				if data[i][j] == 0:
					data[i][j] = 1
					switched.append(j)
			go(cnt + 1, i + 1)
			for j in switched:
				data[i][j] = 0


# 보호 필름의 두께 D, 가로크기 W, 합격기준 K
for test in range(1, int(input()) + 1):
	d, w, k = map(int, input().split())
	data = [list(map(int, input().split())) for _ in range(d)]
	answer = 987654321
	if k == 1:
		print('#{} {}'.format(test, 0))
	else:
		go(0, 0)
		print('#{} {}'.format(test, answer))

 

추가 일자. 2021 10. 17

def check_column(col: int) -> bool:
    """열을 확인한다.

    Args:
        col (int): 열을 확인한다.

    Returns:
        bool: k개 이상일 경우 성립 문제 조건
    """
    cnt = 1
    for i in range(1, d):
        if data[i-1][col] == data[i][col]:
            cnt += 1
            if cnt >= k:
                return True
        else:
            cnt = 1
    return False


def check() -> bool:
    """열을 계산한다.

    Returns:
        bool: 체크 여부 확인
    """
    for col in range(w):
        if not check_column(col):
            return False
    return True


def go(cnt: int, row: int) -> None:
    """조합을 통해서 확인한다.

    Args:
        cnt (int): 현재 칠한 갯수
        row (int): 가능한 행
    """
    global answer
    if cnt >= answer:
        return

    if check():
        answer = min(answer, cnt)
        return
    else:
        for i in range(row, d):
            switched = data[i][::]
            data[i] = [0]*w
            go(cnt + 1, i + 1)
            data[i] = switched[::]

            switched = data[i][::]
            data[i] = [1]*w
            go(cnt + 1, i + 1)
            data[i] = switched[::]


# 보호 필름의 두께 D, 가로크기 W, 합격기준 K
for test in range(1, int(input()) + 1):
    d, w, k = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(d)]
    answer = 987654321
    if k == 1:
        print('#{} {}'.format(test, 0))
    else:
        go(0, 0)
        print('#{} {}'.format(test, answer))