[파이썬] SWEA SW 문제해결 응용 7일차 - 행렬찾기

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18LoAqItcCFAZN 

SW Expert Academy

 

일단 이건 예제에 있는 테케이다...

1
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

 

 

일단 주어진 array를 2중 for문을 돌면서 탐색하고, 행렬이 있는 자리는 used 배열을 사용할 것이다.

그리고 행렬의 가로, 세로 길이를 탐는 result 배열 또한 만들어준다.

또한, 부분행렬을 세는 변수 cnt도 만든다.

T = int(input())
 
for tc in range(1, 1+T):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    used = [[0]*N for _ in range(N)]
    cnt = 0
    result = []
 
    for i in range(N):
        for j in range(N):
            if arr[i][j] != 0 and used[i][j] == 0:
                cnt += 1
                findmatrix(i, j)

2중 for문을 돌면서 

아직 지나온 적이 없으면서 (used배열의 좌표값이 0이면서)

배열의 값이 0이 아니면, 

cnt에 1을 추가하고 함수를 실행한다.

 

 

<함수에 대한 설명>

주어진 조건 1에서 

사각형 내부에는 빈 용기가 없다고 했기 때문에, 

가로와 세로 길이를 알기만 하면 그 사이에 있는 값들은 모두 0이 아님을 알 수 있다.

그래서 모든 좌표가 0인 used 배열을 만들고, 

가로의 첫 시작 좌표와 세로의 끝 좌표 사이 좌표들은 모두 1으로 바꾸고, 

세로도 마찬가지로 하는 함수를 만들었다.

 

def findmatrix(y, x):
    used[y][x] = 1
    k = 0
    j = 0
   	# 가로 
    while True:
        k += 1
        nx = x+k
        if nx < N and used[y][nx] == 0 and arr[y][nx] != 0:
            used[y][nx] = 1
        else:
            nx -= 1
            break
 	#세로
    while True:
        j += 1
        ny = y + j
        if ny < N and arr[ny][nx] != 0 and used[ny][nx] == 0:
            used[ny][nx] = 1
        else:
            ny -= 1
            break
 
    for a in range(y, ny + 1):
        for b in range(x, nx + 1):
            used[a][b] = 1
 
    result.append([j, k])

 

마지막으로, 부분행렬은 크기가 작은 순서대로 출력하기 때문에 sort를 해준다.

    result = sorted(result, key=lambda x: (x[0] * x[1], x[0]))
    result = sum(result, [])
    print(f'#{tc} {len(result) // 2}', end=" ")
 
    for i in range(len(result)):
        print(result[i], end=" ")
    print()

 

 

 

전체 풀이)

def findmatrix(y, x):
    used[y][x] = 1
    k = 0
    j = 0
    while True:
        k += 1
        nx = x+k
        if nx < N and used[y][nx] == 0 and arr[y][nx] != 0:
            used[y][nx] = 1
        else:
            nx -= 1
            break
 
    while True:
        j += 1
        ny = y + j
        if ny < N and arr[ny][nx] != 0 and used[ny][nx] == 0:
            used[ny][nx] = 1
        else:
            ny -= 1
            break
 
    for a in range(y, ny + 1):
        for b in range(x, nx + 1):
            used[a][b] = 1
 
    result.append([j, k])
 
 
T = int(input())
 
for tc in range(1, 1+T):
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    used = [[0]*N for _ in range(N)]
    cnt = 0
    result = []
 
    for i in range(N):
        for j in range(N):
            if arr[i][j] != 0 and used[i][j] == 0:
                cnt += 1
                findmatrix(i, j)
 
    result = sorted(result, key=lambda x: (x[0] * x[1], x[0]))
    result = sum(result, [])
    print(f'#{tc} {len(result) // 2}', end=" ")
 
    for i in range(len(result)):
        print(result[i], end=" ")
    print()