Study/SW Expert
[Python] SW Expert 1258. 7일차 - 행렬찾기
devyoseph
2022. 2. 2. 11:12
- 시간 : 10개 테스트케이스를 합쳐서 C++의 경우 10초 / Java의 경우 10초 / Python의 경우 20초
- 메모리 : 힙, 정적 메모리 합쳐서 256MB 이내, 스택 메모리 1MB 이내
※ SW Expert 아카데미의 문제를 무단 복제하는 것을 금지합니다.
링크: https://swexpertacademy.com/main/solvingProblem/solvingProblem.do
유엔 화학 무기 조사단이 대량 살상 화학 무기를 만들기 위해 화학 물질들이 저장된 창고를 조사하게 되었다.
창고에는 화학 물질 용기 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 순으로 출력한다.
[풀이]
문제 풀이가 생각보다 오랜 시간이 걸렸기 때문에 리뷰를 할 수 밖에 없던 문제였습니다.
1. dfs 탐색
사각형을 찾기 위해 어느 구역(범위)를 탐색해야하며 탐색 경로가 겹치지 않는 것이 매우 중요했습니다. 이 때문에 구역찾기에서 많이 사용하는 dfs를 이용해 연결된 면적을 모두 방문체크해 기록하는 방식을 사용했습니다.
dx = [1,-1,0,0]
dy = [0,0,1,-1] # 상하좌우 좌표 저장
check = [[False for i in range(n)] for j in range(n)] # 방문체크 배열
def dfs(row, col): # 재귀를 통해 연결된 구역들 표시
if row < 0 or row >= n or col < 0 or col >= n or lst[row][col] ==0 or check[row][col]:
return # 경계값을 벗어나면 종료
check[row][col] = True # 방문 체크
for direction in range(4): # 상하좌우 검색
dfs(row+dx[direction],col+dy[direction])dfs를 사용해 연결된 곳을 사슬처럼 쭉 체크해준다면 배열을 0,0부터 탐색할 때 이후 탐색했던 면적을 중복해서 탐색하지 않아도 됩니다.
2. 사각형의 행,렬 최대 길이 구하기
현재 탐색을 시작하는 곳은 0이 아닌 지점입니다.
1) 오른쪽으로 쭉 이동하면서 0이나 경계값을 만날 때까지 이동하고 멈춘다면 그 때의 index를 구합니다. (열의 최대값)
1) 아래쪽으로 쭉 이동하면서 0이나 경계값을 만날 때까지 이동하고 멈춘다면 그 때의 index를 구합니다. (행의 최대값)
3. 최대 행,열 값을 가지고 내부와 외부를 검사
1) 내부 검사: 처음 위치와 2번에서 구한 최대 index값을 기준으로 내부 원소들이 모두 0이 아닌 숫자인지 판별합니다.
2) 외부 검사: 경계값이 모두 0인지 판별합니다.
def recIn(row,col,row_max,col_max): # 내부 검사 메소드
for i in range(row,row_max):
for j in range(col,col_max):
if lst[i][j] == 0:
return False
return True
def recOut(row,col,row_max,col_max): # 외부 검사 메소드
if row-1 >= 0: # 위쪽 경계 체크
for j in range(col,col_max):
if lst[row-1][j] != 0:
return False
if row_max <= n-1: # 아래쪽 경계
for j in range(col,col_max):
if lst[row_max][j] != 0:
return False
if col-1 >= 0: # 왼쪽 경계
for i in range(row,row_max):
if lst[i][col-1] != 0:
return False
if col_max <= n-1: # 오른쪽 경계
for i in range(row,row_max):
if lst[i][col_max] != 0:
return False
return True
전체 코드
dx = [1,-1,0,0]
dy = [0,0,1,-1] # 상하좌우 검색용 좌표
for t in range(int(input())):
n = int(input())
lst = []
cnt = 0
answer = []
check = [[False for i in range(n)] for j in range(n)]
for l in range(n): # 값 집어넣기
lst.append(list(map(int,input().split())))
def dfs(row, col): # 재귀를 통해 연결된 구역들 표시
if row < 0 or row >= n or col < 0 or col >= n or lst[row][col] ==0 or check[row][col]:
return # 경계값을 벗어나면 종료
check[row][col] = True # 방문 체크
for direction in range(4): # 상하좌우 검색
dfs(row+dx[direction],col+dy[direction])
def getlegth(row,col): # 현재 사각형의 최대 길이를 구하는 메소드
row_max = row
col_max = col
while row_max < n:
if lst[row_max][col] == 0:
break
row_max += 1
while col_max < n:
if lst[row][col_max] == 0:
break
col_max += 1
return row_max,col_max
def recIn(row,col,row_max,col_max): # 내부가 온전한 사각형인지 구하는 메소드
for i in range(row,row_max):
for j in range(col,col_max):
if lst[i][j] == 0:
return False
return True
def recOut(row,col,row_max,col_max): # 외부가 0인지 확인해주는 메소드
if row-1 >= 0: # 위쪽 경계 체크
for j in range(col,col_max):
if lst[row-1][j] != 0:
return False
if row_max <= n-1: # 아래쪽 경계
for j in range(col,col_max):
if lst[row_max][j] != 0:
return False
if col-1 >= 0: # 왼쪽 경계
for i in range(row,row_max):
if lst[i][col-1] != 0:
return False
if col_max <= n-1: # 오른쪽 경계
for i in range(row,row_max):
if lst[i][col_max] != 0:
return False
return True
for i in range(n): # 배열 전체탐색
for j in range(n):
if lst[i][j] != 0 and not check[i][j]:
dfs(i,j)
row_max, col_max = getlegth(i,j)
if recIn(i,j,row_max,col_max) and recOut(i,j,row_max,col_max):
cnt += 1
answer.append([row_max-i,col_max-j])
# 답 출력하는 곳
answer.sort(key=lambda x: x[0]) # 먼저 행으로 정렬 후
answer.sort(key=lambda x:x[0]*x[1]) # 넓이로 정렬
dap = ''
for i in answer:
for j in i:
dap += str(j) + ' '
print(f'#{t+1} {cnt} {dap}')