[구름 | 2단계] 놀이공원(완전탐색, 구현)

https://level.goorm.io/exam/88520/%EB%86%80%EC%9D%B4%EA%B3%B5%EC%9B%90/quiz/1

 

어느 한 도시에서는 공장 단지가 부도가 나게 되어 넓은 공터가 경매에 올라오게 되었다. 이 공터는 가로와 세로가 각각 N km인 정사각형 모양이며 가로와 세로가 1 km인 정사각형 격자 모양으로 영역을 나누어 개별적으로 판매하고 있다. 

 그 도시에 살고있던 한 부자 경영인은 평소 자신이 기획해오던 놀이공원 건설 프로젝트를 몰래몰래 진행하기로 결정하였다. 때마침 경매에 올라온 이 공터에 관심을 가지게 된 경영인은 판매 중인 땅들 중 일부에는 기존의 공장에서 배출 된 폐기물들이 방치되어 있다는 사실을 알게 되었다. 놀이공원 건설을 위해서는 가로로 K km, 세로로 K km인 정사각형 모양의 영역이 필요한데, 당연히 놀이공원 건설을 위해서는 해당 영역의 폐기물들을 모두 처리해야만 한다.

 

<N=5, K=3일 때 - 파란색 영역을 선택하면 3개를, 빨간색 영역을 선택하면 1개의 폐기물을 처리해야 한다.>

 

 NxN 격자 모양의 공터에서 KxK 정사각형 크기의 땅을 구매하려고 할 때, 구매할 땅에 포함 된 폐기물의 수를 최소로 할 수 있는 영역을 찾을 수 있는 프로그램을 작성해주자.

 

입력 형식

 첫 줄에는 테스트케이스의 수를 나타내는 1이상 100이하의 자연수 T가 주어진다.

각 테스트케이스의 첫 줄에는 두 자연수 공터의 크기를 나타내는 N과 구매할 땅의 크기를 나타내는 K가 주어진다.

• N은 1이상 100이하의 자연수이다.
• K는 1이상 10이하의 자연수이다. K는 N보다 작거나 같은 값을 가진다.

이후 N줄에 걸쳐서 공터의 각 행의 정보가 차례로 주어진다.

• 각 줄은 공백으로 구분 된 0과 1이 총 N개 주어진다.
• 0은 비어있는 땅을 나타내며, 1은 폐기물이 존재하는 칸을 나타낸다.

 

출력 형식

 각 테스트케이스에 대하여 KxK 모양의 땅을 구매했을 때 얻을 수 있는 최소의 폐기물의 수를 공백없이 한 줄에 출력한다.

 

문제 출처

• 구름EDU - 알고리즘 문제해결기법 입문

 

:

공백

 

:

줄바꿈

 

:

탭

예시 1

입력

 

1
53
10010
01001
00010
00000
00100

출력

 

1

⋇ 입출력 형식을 잘 지켜주세요

 

testCase = int(input())

for _ in range(testCase) :
	n, k = map(int, input().split())
	board = []

	for i in range(n) :
		line = list(map(int, input().split()))
		board.append(line)

	garbaseCountList = []
	for i in range(n - k + 1) :
		for j in range(n - k + 1) :
			garbaseCount = 0
			for r in range(k):
				for c in range(k) :
					if board[i + r][j + c] == 1 :				#쓰레기인경우
						garbaseCount += 1									#쓰레기 개수 증가
			garbaseCountList.append(garbaseCount)
		
	print(min(garbaseCountList))