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

문제 출처 : SW Expert Academy

문제

창고의 용기들에 대한 2차원 배열에서 행렬(화학 물질이 든 용기들로 이루어진 사각형)들을 찾아내고 정보를 수집하고자 한다.

찾아낸 행렬들의 정보를 출력하는 프로그램을 작성.

코드

# 0828
import sys
sys.stdin = open('input.txt')
# A는 3x4, B는 2x3, C는 4x5
# 찾아낸 행렬들의 정보를 출력하는 프로그램
# 출력 = #tc 행렬개수 행렬행 행렬열 ...(행*열 크기 작은 값부터)

def search(arr):
    global N

    q = []
    visited = [[0 for _ in range(N)] for _ in range(N)]

    start_arr = []
    end_arr = []
    result = []
    cnt = 0

    # 오른쪽, 아래
    dx = [0, +1]
    dy = [+1, 0]

    for i in range(N):
        for j in range(N):
            # 0이 아닌 경우 q에 넣고
            if arr[i][j] != 0 and visited[i][j] == 0:
                q.append([i, j])
                visited[i][j] = 1
                start_arr.append([i, j])
            # 스타트 지점 인덱스 저장
                while q:
                    v = q.pop(0)
                    visited[v[0]][v[1]]

                    for k in range(2):
                        new_x = v[0] + dx[k]
                        new_y = v[1] + dy[k]
                        if 0 <= new_x < N and 0 <= new_y < N:
                            if arr[new_x][new_y] != 0:
                                if visited[new_x][new_y] == 0:
                                    q.append([new_x, new_y])
                                    visited[new_x][new_y] = 1
                    if len(q) == 0:
                        end_arr.append(v)
                        cnt += 1

    # 화학용기 행렬계산
    for row in range(len(start_arr)):
        result_x = end_arr[row][0] - start_arr[row][0] + 1
        result_y = end_arr[row][1] - start_arr[row][1] + 1

        result.append(result_x)
        result.append(result_y)

    return cnt, result

# 행*열 크기 순으로 재정렬
def ans(result):
    real_result = []
    mix_arr = []
    # 행렬 곱한 값들 저장(index, 곱한값)
    for m in range(len(result)//2):
        mix = result[2*m] * result[2*m+1]
        mix_arr.append([2*m, mix])

    # 작은순으로 정렬
    for v in range(len(mix_arr)):
        for w in range(len(mix_arr)-1):
            # 곱한 값이 같다면
            if mix_arr[w][1] == mix_arr[w+1][1]:
                # 행렬크기의 행값 비교
                if result[mix_arr[w][0]] > result[mix_arr[w+1][0]]:
                    mix_arr[w], mix_arr[w + 1] = mix_arr[w + 1], mix_arr[w]
            # 곱한 값이 크다면
            if mix_arr[w][1] > mix_arr[w+1][1]:
                mix_arr[w], mix_arr[w + 1] = mix_arr[w+1], mix_arr[w]
    # 행렬 리스트 정렬
    for h in range(len(mix_arr)):
        index = mix_arr[h][0]
        real_result.append(result[index])
        real_result.append(result[index+1])
    return real_result


T = int(input())

for tc in range(1,T+1):
    # 행렬 NxN
    N = int(input())
    arr = [list(map(int, input().split())) for _ in range(N)]
    cnt = search(arr)[0]
    result = search(arr)[1]

    print("#{} {}".format(tc, cnt), end =' ')
    print(*ans(result))

장애물

1. 코드가 길어지길래 스스로 의심이 들기 시작.. 이거 맞나..?
2. 문제의 조건을 한가지 빼먹어서 테스트 케이스 8/10 error 발생
   +비교하는 값을 잘못 지정했다.

  # 작은순으로 정렬
    for v in range(len(mix_arr)):
        for w in range(len(mix_arr)-1):
	# 행렬크기의 행값 비교
            if mix_arr[w][1] > mix_arr[w+1][1]:
                mix_arr[w], mix_arr[w + 1] = mix_arr[w+1], mix_arr[w]

문제점

• 곱한 값이 같은 경우에 처리코드가 빠져있다.
• 행렬 크기의 행값 비교 주석부분 코드는
  행값을 비교하는 것이 아니라 result에 들어있는 행값의 인덱스 값을 비교하는 코드였다.

해결코드

 # 작은순으로 정렬
    for v in range(len(mix_arr)):
        for w in range(len(mix_arr)-1):
            # 곱한 값이 같다면
            if mix_arr[w][1] == mix_arr[w+1][1]:
                # 행렬크기의 행값 비교
                if result[mix_arr[w][0]] > result[mix_arr[w+1][0]]:
                    mix_arr[w], mix_arr[w + 1] = mix_arr[w + 1], mix_arr[w]
            # 곱한 값이 크다면
            if mix_arr[w][1] > mix_arr[w+1][1]:
                mix_arr[w], mix_arr[w + 1] = mix_arr[w+1], mix_arr[w]