[SWEA] D4 1258 행렬찾기 (Python)

출처

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

문제

유엔 화학 무기 조사단이 대량 살상 화학 무기를 만들기 위해 화학 물질들이 저장된 창고를 조사하게 되었다.

창고에는 화학 물질 용기 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

[입력]

맨 첫 줄에는 테스트 케이스의 개수가 주어진다.

그리고 테스트 케이스가 각 라인에 주어진다.

각 테스트 케이스는 (n+1) 줄로 구성되며, 첫 줄에는 양의 정수인 n이 주어지고, 다음 n줄에는 n x n 행렬이 (각 행이 한 줄에) 주어진다.

[출력]

각 테스트 케이스 각각에 대한 답을 출력한다.

각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음, 각 테스트 케이스에 주어진 행렬에서 추출된 부분 행렬들을 개수와 그 뒤를 이어 행렬들의 행과 열의 크기를 출력한다.

크기는 행과 열을 곱한 값으로, 크기가 작은 순서대로 출력한다.

예를 들어 3x4 행렬의 크기는 3*4 = 12 이다.

크기가 같을 경우 행이 작은 순으로 출력한다.

예를 들어 12x4, 8x6 두 개의 행렬은 같은 크기이고 행은 각각 12, 8 이므로 8 6 12 4 순으로 출력한다.

10 9 1 1 3 2 0 0 0 0 0 3 2 5 2 0 0 0 0 0 2 3 3 1 0 0 0 0 0 0 0 0 0 4 5 5 3 1 1 2 5 0 3 6 4 2 1 2 3 6 0 2 1 1 4 2 0 0 0 0 4 2 3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 1 2 0 0 0 0 0 0 9 4 2 0 1 7 3 0 …

#1 3 2 3 3 4 4 5 #2 2 1 2 2 3 …

 

풀이

뭔가 획기적인 아이디어가 떠오르지 않아 그냥 단순무식하게 완전탐색해버렸다.

0이 아닌 지점을 찾았으면 그 x,y좌표부터 시작해 좌,우,아래 방향을 탐색하며 0이 아닌 지점을 찾아갔으며 한번 방문한 곳은 0으로 만들어 중복으로 방문하는것을 방지하였다. 행렬의 행과 열의 크기는 탐색지점에서 최초시작 x, y를 뺀 최대값으로 생각하고 풀었음.

key 값 기준 정렬방식

(1) itemgetter

from operator import itemgetter
result = [(3, 4), (2, 3), (4, 5)]
sorted_result = sorted(result,key=itemgetter(0*1,0)) 
>>> result = [(2,3), (3,4), (4,5)]

• 요소의 0번째 = result / 1번째 = key
• result * key를 기준으로 정렬
• 그 후 key를 기준으로 정렬

(2) lambda식 사용

result = [(3, 4), (2, 3), (4, 5)]
sorted_result = sorted(result,key= lambda x: (x[0]*x[1],x[0]))
>>> result = [(2,3), (3,4), (4,5)]

https://docs.python.org/3.7/howto/sorting.html#sortinghowto

>> 여기서 더 자세히 알 수 있음!

코드

#from operator import itemgetter
def search(row, col):
    global X
    global Y
    dx = [0, 0, 1]  # 우 좌 하
    dy = [1, -1, 0]
    mapp[row][col] = 0 # 다녀간곳은 0으로 바꿔줌 왔던 곳 중복으로 방문하는 것을 방지하기 위함
    for i in range(3):
        if 0 <= row+dx[i] < n and 0 <= col+dy[i] < n and mapp[row+dx[i]][col+dy[i]] != 0: 
            if row+dx[i] - init_x + 1 >= X: # 길이가 최대인 부분이 행렬의 세로 길이
                X = row+dx[i] - init_x + 1
            if col+dy[i] - init_y >= Y: # 길이가 최대인 부분이 행렬의 가로 길이
                Y = col+dy[i] - init_y + 1
            search(row+dx[i], col+dy[i])
    return X, Y
 
T = int(input())
for t in range(T):
    n = int(input())
    mapp = []
    cnt = 0 # 행렬 개수 카운팅
    result = []
    for _ in range(n):
        mapp.append(list(map(int, input().split())))
 
    for y in range(n):
        for x in range(n):
            if mapp[x][y] != 0: # 0이 아닌 부분이 있으면 탐색 시작할꺼임
                cnt += 1 
                X = 0 # 결과값에 들어갈 행
                Y = 0 # 결과값에 들어갈 열
                init_x = x # 최초행
                init_y = y # 최초열
                result.append(search(x, y))
    sorted_result = sorted(result,key= lambda x: (x[0]*x[1],x[0]))
    # sorted_result = sorted(result,key=itemgetter(0*1,0))
    print(f'#{t+1}',cnt, end =" ")
    for i in range(len(sorted_result)):
        print(*sorted_result[i],end =" ")
    print()

아쉬운점

search라는 함수를 사용해 탐색을 하면서 행의 길이와 열의 길이를 구했는데 매번 탐색 시점에서의 행과 열의 길이를 최대값인지 아닌지 비교하는 방식밖에 떠오르지 않아 이렇게 풀긴했지만 비효율적인거 같아 아쉽다...