문제 : [S/W 문제해결 응용] 7일차 - 행렬찾기
문제
유엔 화학 무기 조사단이 대량 살상 화학 무기를 만들기 위해 화학 물질들이 저장된 창고를 조사하게 되었다.
창고에는 화학 물질 용기 n2개가 n x n으로 배열되어 있었다.
유엔 조사단은 각 용기를 조사하여 2차원 배열에 그 정보를 저장하였다.
빈 용기에 해당하는 원소는 ‘0’으로 저장하고, 화학 물질이 들어 있는 용기에 해당하는 용기는 화학 물질의 종류에 따라 ‘1’에서 ‘9’사이의 정수를 저장하였다.
다음 그림은 창고의 화학 물질 현황을 9x9 배열에 저장한 예를 보여준다.
유엔 조사단은 화학 물질이 담긴 용기들로부터 3가지 사항을 발견하였다.
- 화학 물질이 담긴 용기들이 사각형을 이루고 있다. 또한, 사각형 내부에는 빈 용기가 없다.
예를 들어, 위의 그림에는 3개의 화학 물질이 담긴 용기들로 이루어진 사각형 A, B, C가 있다.
- 화학 물질이 담긴 용기들로 이루어진 사각형들은 각각 차원(가로의 용기 수 x 세로의 용기 수)이 다르다.
예를 들어, 위의 그림에서 A는 3x4, B는 2x3, C는 4x5이다.
- 2개의 화학 물질이 담긴 용기들로 이루어진 사각형들 사이에는 빈 용기들이 있다.
예를 들어, 위의 그림에서 A와 B 사이와 B와 C 사이를 보면, 빈 용기를 나타내는 ‘0’ 원소들이 2개의 사각형 사이에 있는 것을 알 수 있다.
단, A와 C의 경우와 같이 대각선 상으로는 빈 용기가 없을 수도 있다.
유엔 조사단은 창고의 용기들에 대한 2차원 배열에서 행렬(화학 물질이 든 용기들로 이루어진 사각형)들을 찾아내고 정보를 수집하고자 한다.
찾아낸 행렬들의 정보를 출력하는 프로그램을 작성하시오.
제약 사항
n은 100 이하이다.
부분 행렬의 열의 개수는 서로 다르며 행렬의 행의 개수도 서로 다르다.
예를 들어, 3개의 부분행렬 행렬 (A(3x4), B(2x3), C(4x5))이 추출되었다면, 각 부분 행렬의 행의 수는 3, 2, 4로 서로 다르다.
마찬가지로 각 부분 행렬의 열의 수도 4, 3, 5로 서로 다르다.
테스트 케이스는 여러 개의 그룹으로 구성되며 아래와 같다.
그룹 1. n <= 10 이고 sub matrix의 개수 5개 이하
그룹 2. n <= 40 이고 5 < sub matrix <= 10
그룹 3. 40 < n <=80 이고 5 < sub matrix <= 10
그룹 4. 40 < n <=80 이고 10 < sub matrix <= 15
그룹 5. 80 < n<=100 이고 15 < sub matrix <= 20
입력
맨 첫 줄에는 테스트 케이스의 개수가 주어진다.
그리고 테스트 케이스가 각 라인에 주어진다.
각 테스트 케이스는 (n+1) 줄로 구성되며, 첫 줄에는 양의 정수인 n이 주어지고, 다음 n줄에는 n x n 행렬이 (각 행이 한 줄에) 주어진다.
출력
각 테스트 케이스 각각에 대한 답을 출력한다.
각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음, 각 테스트 케이스에 주어진 행렬에서 추출된 부분 행렬들을 개수와 그 뒤를 이어 행렬들의 행과 열의 크기를 출력한다.
크기는 행과 열을 곱한 값으로, 크기가 작은 순서대로 출력한다.
예를 들어 3x4 행렬의 크기는 3*4 = 12 이다.
크기가 같을 경우 행이 작은 순으로 출력한다.
예를 들어 12x4, 8x6 두 개의 행렬은 같은 크기이고 행은 각각 12, 8 이므로 8 6 12 4 순으로 출력한다.
예제 입력
2 #테스트 케이스의 개수
5 # N (N X N행렬)
1 2 3 4 0 # 이 다음부터 N번째 줄 까지 N X N 행렬의 숫자들
0 0 0 0 0
5 0 0 0 0
6 0 0 0 0
0 0 0 0 0
8
1 2 3 0 0 4 5 0
6 7 8 0 0 0 0 0
9 1 2 0 0 3 0 0
4 5 6 0 0 7 0 0
0 0 0 0 0 8 0 0
9 1 2 3 0 4 0 0
5 6 7 8 0 9 0 0
0 0 0 0 0 0 0 0
...
예제 출력
#1 2 2 1 1 4
#2 4 1 2 5 1 2 4 4 3
...
문제 해석
NXN 박스 안에 직사각형 형태로 숫자들(화학 물질 용기)이 0과 함께 조합되어 있다. 입력값을 확인해 보자. 처음에는 테스트 케이스 개수가 주어지고, 다음에는 N과 N x N행렬의 숫자들을 입력한다. 이를 토대로 초기값을 설정해 보자.
|
1
2
3
4
5
|
T = int(input())
for Count in range(T):
print("#{0} ".format(Count+1),end='')
N = int(input())
List = [list(map(int,input().split())) for _ in range(N)]
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
처음에 T를 입력 받아주고, T 횟수만큼 Count해준다. 한 번 실행할 때마다 N과 List를 받아주어야 하며, List는 한 줄씩 띄어쓰기 단위로 리스트를 만들어주고, 이를 N회 반복하여 2차 리스트로 받아준다.
|
1
2
|
for i in List:
print(*i)
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
를 실행해보면 아래와 같은 결과를 확인해 볼 수 있으니 중간중간 확인해 보면 좋다.
1 2 3 4 0
0 0 0 0 0
5 0 0 0 0
6 0 0 0 0
0 0 0 0 0 이제 다음으로 생각해보아야 할 것이 박스의 크기이다. 리스트를 훑어보면서 만약 0이 아닌 값을 만난다면 그 박스의 크기를 구해야 할 것이다. 다행히 박스는 직사각형으로 가로 길이와 세로길이를 구하면 된다. 길이를 다 찾으면 해당하는 리스트 값들을 0으로 변형시켜야 다음에 새로운 직사각형을 찾을 때 기존의 값과 중복되지 않을거라 생각하여 다음과 같이 코딩을 하였다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
def box(y,x):
global LY,LX
dy = [0,1]
dx = [1,0]
for i in range(2):
C_Y = y + dy[i]
C_X = x + dx[i]
if List[C_Y][C_X]:
if i :
LY += 1
else:
LX += 1
return box(C_Y,C_X)
for Count in range(T):
print("#{0} ".format(Count+1),end='')
N = int(input())
List = [list(map(int,input().split())) for _ in range(N)]
Basket = []
count = 0
for Y in range(N):
for X in range(N):
if List[Y][X]:
count += 1
LY = LX = 1
box(Y,X)
for y in range(LY):
for x in range(LX):
List[Y+y][X+x] = 0
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
count는 화학 물질 박스의 갯수 이고, LX는 가로 길이, LY는 세로 길이이다. 그리고 만약 `List[Y][X]`의 값이 0이 아닌 수라면, 그 때 box라는 함수로 들어가 가로 길이와 세로 길이를 뽑을 수가 있다.
이렇게 하여 모든 `List` 안의 화학 물질의 가로 세로 길이를 확인 할 수가 있다. 이제 이 값들을 Basket이라는 리스트 안에 담아서 저장하도록 하자. 가로, 세로길이를 같이 저장하기 위해서 `[LY,LX]` 형태로 저장하였기에 Basket은 2중 리스트가 되었다. Basket에 append 시키는 것은`box(y,x)` 이후에 바로 한다.
그러면 Basket의 결과값으로 `[[1, 4], [2, 1]]`를 확인할 수 있고 이는 가로의 길이 1, 세로의 길이가 4인 박스와 가로의 길이 2, 세로의 길이 1인 박스 2개를 확인할 수 있다.
다음 작업으로, 박스의 넓이를 따져야 한다. 박스의 넓이가 큰 것은 뒤로, 작은 것은 앞으로 리스트를 정렬해야 한다. 이를 위해 새로운 리스트 Answer를 만들었고, 정렬 방식은 3가지로 나누었다.
- Answer의 초기값은 Basket의 첫번째 값이다.
- Basket 값의 뒤에서 부터 확인하여 만약 Basket의 넓이가 Answer안의 값보다 크면 해당 Answer의 값에 Basket을 삽입시킨다.
- 만약 Answer과 Basket의 넓이가 같다면 세로의 길이가 짧은 것이 앞으로 가도록 삽입한다.
이와 같이 계획하여 코딩을 해보자.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
Answer = [Basket[0][0],Basket[0][1]]
if len(Basket)>1:
for i in range(1,len(Basket)): # Basket 리스트가 한개짜리면 에러가 뜨겟지
for j in range(len(Answer)//2-1,-1,-1):
if Answer[0] * Answer[1] > Basket[i][0]*Basket[i][1]:
Answer = [Basket[i][0],Basket[i][1]] + Answer
break
elif Basket[i][0]*Basket[i][1] > Answer[2*j]*Answer[2*j+1]:
break
elif Basket[i][0]*Basket[i][1] == Answer[2*j]*Answer[2*j+1]:
if i<j:
if i>j:
break
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
모든 코딩을 완료하였다. 결과를 확인해보고, SWExpert에 제출해보자. 다행히 Pass를 받을 것이다.
끝으로 모든 코드를 공개하고 포스팅을 마치겠다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
T = int(input())
def box(y,x):
global LY,LX
dy = [0,1]
dx = [1,0]
for i in range(2):
C_Y = y + dy[i]
C_X = x + dx[i]
if List[C_Y][C_X]:
if i :
LY += 1
else:
LX += 1
return box(C_Y,C_X)
for Count in range(T):
print("#{0} ".format(Count+1),end='')
N = int(input())
List = [list(map(int,input().split())) for _ in range(N)]
Basket = []
count = 0
for Y in range(N):
for X in range(N):
if List[Y][X]:
count += 1
LY = LX = 1
box(Y,X)
for y in range(LY):
for x in range(LX):
List[Y+y][X+x] = 0
print(count,end=' ')
Answer = [Basket[0][0],Basket[0][1]]
if len(Basket)>1:
for i in range(1,len(Basket)):
for j in range(len(Answer)//2-1,-1,-1):
if Answer[0] * Answer[1] > Basket[i][0]*Basket[i][1]:
Answer = [Basket[i][0],Basket[i][1]] + Answer
break
elif Basket[i][0]*Basket[i][1] > Answer[2*j]*Answer[2*j+1]:
break
elif Basket[i][0]*Basket[i][1] == Answer[2*j]*Answer[2*j+1]:
if i<j:
if i>j:
break
print(*Answer)
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
더 간략하게 짤 수 있는 방법 있으면 알려주세요!! 아직 초보자라 직관적으로 풀었습니다.
출처
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
'SWExpert > D4' 카테고리의 다른 글
| [D4] 1486. 장훈이의 높은 선반 (Python 파이썬 풀이) (0) | 2020.02.28 |
|---|