[SWEA][D4] 1258. [S/W 문제해결 응용] 7일차 - 행렬찾기 파이썬

📖 [D4] 1258.[S/W 문제해결 응용] 7일차 - 행렬찾기 D4 파이썬

 

유엔 화학 무기 조사단이 대량 살상 화학 무기를 만들기 위해 화학 물질들이 저장된 창고를 조사하게 되었다.ㅡ창고에는 화학 물질 용기 n2개가 n x n으로 배열되어 있었다.
유엔 조사단은 각 용기를 조사하여 2차원 배열에 그 정보를 저장하였다.
빈 용기에 해당하는 원소는 ‘0’으로 저장하고, 화학 물질이 들어 있는 용기에 해당하는 용기는 화학 물질의 종류에 따라 ‘1’에서 ‘9’사이의 정수를 저장하였다.
다음 그림은 창고의 화학 물질 현황을 9x9 배열에 저장한 예를 보여준다.

 

유엔 조사단은 화학 물질이 담긴 용기들로부터 3가지 사항을 발견하였다.
1. 화학 물질이 담긴 용기들이 사각형을 이루고 있다. 또한, 사각형 내부에는 빈 용기가 없다.
예를 들어, 위의 그림에는 3개의 화학 물질이 담긴 용기들로 이루어진 사각형 A, B, C가 있다.
2. 화학 물질이 담긴 용기들로 이루어진 사각형들은 각각 차원(가로의 용기 수 x 세로의 용기 수)이 다르다.
예를 들어, 위의 그림에서 A는 3x4, B는 2x3, C는 4x5이다.
3. 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

---

✍ < 구성 과정 - 고려 사항>

1. 가로랑 세로를 어떻게 수를 세서 한 쌍으로 묶을 것인가 

>>0이나 벽으로 네모를 구분하고, 각 네모들의 가로의 길이/세로의 길이가 서로 다르다는 것을 이용하고자 함

 

2. 출력요구조건 대로 정렬을 어떻게 해서 뽑아 낼 것인가

>>시도. 리스트 속 리스트[[2차원배열]] or 리스트 속 튜플[(),()...]이 있을 때, sort() 함수를 쓰면 어떻게 정렬이 되는지 확인

정렬 순서를 확인해 보고, 이를 토대로 넓이순, 가로순이 되도록 구성

 

💡 <PASS>

T = int(input())
for t in range(1,T+1):
    
    n = int(input()) # nxn 크기
    dic = {} # 가로가 키요, 세로가 값이요
    arr = [list(map(int,input().split()))for _ in range(n)]
    for y in range(n):
        cnt = 0
        for x in range(n):
            if arr[y][x] > 0:
                cnt += 1
            elif arr[y][x] == 0 and cnt != 0:
                dic[cnt] = dic.get(cnt,0)+1
                cnt = 0
            else: # 없어도 되는 else...
                cnt = 0
        if cnt > 0:
            dic[cnt] = dic.get(cnt,0)+1
    matrix = []
    for garo,sero in dic.items(): # 가로가 키요, 세로가 값이요
        matrix.append((sero*garo,sero,garo))
    matrix.sort()
    print('#{} {}'.format(t,len(matrix)),end=' ')
    for i in range(len(matrix)):
        print(matrix[i][1],matrix[i][2],end=' ')
    print()

 

✍ <코드 설명>

# 1258.[S/W 문제해결 응용] 7일차 - 행렬찾기 D4
# 2020.02.27
 
 
T = int(input()) # 테스트케이스 T
for t in range(1,T+1):
    n = int(input()) # nxn크기
    dic = {} # 최종목표 {키key=가로길이 : 값value=세로길이}
    # 주의 : 모든 사각형의 가로의 값이 다르기 때문에(중복없음) 이를 키값으로 사용가능  
 
    arr = [list(map(int,input().split()))for _ in range(n)]
    # 2차원배열을 한 행 씩 훑으며 1~9의 숫자가 있는지 찾기
    for y in range(n): 
        cnt = 0 # cnt = 가로길이(cnt증가)
        for x in range(n):
            # ((1))행x가 증가하다가, 0 초과(1~9)값이 존재 할 때 수세기
            if arr[y][x] > 0:
                cnt += 1 # (가로길이 카운팅)
            # ((2))행x가 증가하다가, 0을 만났는데 and
            # 그런데 이전에 가로길이가 존재했다. dic에 키로 넣어주며
            # 새로 들어온 키면 값을 1, 이전에 있던 키면 1 증가(세로길이 카운팅)
            elif arr[y][x] == 0 and cnt != 0:
                dic[cnt] = dic.get(cnt,0)+1
                cnt = 0 # 초기화
            # ((3))행x가 증가하다가, 0을 만나면 cnt 하지 않는다.
            # arr[y][x] == 0 and cnt == 0 이면 어차피 초기화 상태라서 필요없는 코드  
            # else:
            #     cnt = 0
        # ((4))행을 다 돌았는데, 0을 못만나고 벽인 경우
        # 벽까지해서 카운팅된 가로길이가 있으면 키값으로 넣어줌.    
        if cnt > 0:
            dic[cnt] = dic.get(cnt,0)+1
 
    matrix = [] # [(넓이, 세로, 가로) 순으로 저장]
    for garo,sero in dic.items():
        matrix.append((sero*garo,sero,garo))
    # 넓이를 기준으로 먼저 sort (넓이가 같다면 자동으로 세로 순으로 정렬)
    matrix.sort()
 
    print('#{} {}'.format(t,len(matrix)),end=' ') #matrix 개수, 즉 화학물질 개수를 print
    for i in range(len(matrix)):
        print(matrix[i][1],matrix[i][2],end=' ') #세로, 가로 순으로 print
    print()

- 주석도움 : 고수재완 

 

 

 

 

 

📌 문제출처 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18LoAqItcCFAZN&categoryId=AV18LoAqItcCFAZN&categoryType=CODE

SW Expert Academy