[코드트리] [시뮬레이션] 겹쳐지지 않는 두 직사각형

https://www.codetree.ai/missions/2/problems/non-overlapping-two-rectangles/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제

n * m크기의 이차원 영역의 각 위치에 정수 값이 하나씩 적혀있습니다. 이 영역 안에서 서로 겹치지 않는 두 직사각형을 적절하게 잡아, 두 직사각형 안에 적힌 숫자들의 총 합을 최대로 하는 프로그램을 작성해보세요. 이때, 각 직사각형의 변들은 격자 판에 평행해야 하고 꼭 2개의 직사각형을 골라야만 하며, 두 직사각형의 경계는 서로 닿아도 됩니다.

예를 들어 다음 그림의 경우에는, 두 직사각형을 적절히 잡아 합을 62 만큼 만들 수 있습니다.

 

입력 형식

첫 번째 줄에는 n과 m이 공백을 사이에 두고 주어지고, 두 번째 줄부터 (n+1)번째 줄까지는 각 행의 숫자가 공백을 사이에 두고 주어집니다.

• 2 ≤ n, m ≤ 5
• -1,000 ≤ 정수 값 ≤ 1,000

출력 형식

겹치지 않게 두 직사각형을 잡았을 때, 얻을 수 있는 최대 합을 출력해주세요.

 

입출력 예제

예제1

입력:

4 5
6 5 4 -3 1
3 -4 -4 14 1
6 1 -3 15 -5
3 -5 1 16 3

 

출력:

63

 

---

 

이런 문제를 보게 되면 먼저 해야하는 것을 번호대로 정리해보면 된다. 

1. board에서 1개의 직사각형 시작점을 고르고 범위를 정한다.

2. 다른 하나의 직사각형 시작점을 고르고 범위를 정한다.

3. 직시각형이 서로 안겹치는지 확인한다.

4. 안겹쳤을 때 합을 다 더하고 저장해둔다.

5. 반복하면서 최대값을 구한다.

 

위 내용을 구현하려다보면 for문을 엄청 써야하면서 스스로 의심을 하게 되거나 

생각은 되는데 실제로 구현하려니 막막하기도 하다. 

이런 구현+시뮬레이션은 그냥 믿고 가야하고 일단 구현을 성공하는데 초점을 둬야한다. 

 

1. 먼저 하나의 직사각형 시작점과 범위를 정해본다.

max_sum = INT_MIN
# (i,j)와 (k,l)을 양쪽 꼭지점으로 하는 첫번째 직사각형을 먼저 정하고 
# 그 중 최댓값을 찾는다.
for i in range(n):
    for j in range(m):
        for k in range(i,n):
            for l in range(j,m):
                max_sum = max(max_sum, find_max_sum_with_rect(i,j,k,l))

print(max_sum)

 (i,j)칸을 시작으로 (k,l)칸으로 끝나는 직사각형을 고를때 최대값을 생각해본다.

 

2. (i,j,k,l)이 정해지면 find_max_sum_with_rect 함수로 다른 직사각형의 위치와 범위를 골라준다. 

# 첫번째 직사각형 (x1,y1,x2,y2)를 양 꼭지점으로 할때,
# 두번째 직사각형을 겹치지 않게 잡아 
# 최대 합을 반환하는 함수 
def find_max_sum_with_rect(x1,y1,x2,y2):
    max_sum = INT_MIN
    for i in range(n):
        for j in range(m):
            for k in range(i,n):
                for l in range(j,m):
                    # overlapped은 겹치면 True 
                    if not overlapped(x1,y1,x2,y2, i,j,k,l):
                        max_sum = max(max_sum, rect_sum(x1,y1,x2,y2)+rect_sum(i,j,k,l))
    return max_sum

 

overlapped 함수를 통해 2 직사각형의 위치가 겹치는지 안겹치는지 확인하고 압겹치면 두 직사각형의 합을 더해주고 그게 최대값이면 업데이트를 해준다. 

 

3. 이때 포인트는 새로운 배열을 만들어 매 확인 때 마다 초기화하고 확인하고 초기화하고 확인하는 함수를 만들어 주는 것이다. 

 

---

최종 코드 

import sys

'''
두 직사각형이 겹쳐지는지 확인하는 새로운 배열을 이용하면 비교적 쉽게 계산할 수 있다. 

'''

def rect_sum(x1, y1, x2, y2):
    return sum([board[i][j] for i in range(x1, x2 + 1) for j in range(y1, y2 + 1)])

def clear_board():
    for i in range(n):
        for j in range(m):
            visited[i][j] = 0
            
def check_board():
    # 동일한 칸을 2개의 직사각형이 모두 포함한다면
    # 겹치게 됩니다.
    for i in range(n):
        for j in range(m):
            if visited[i][j] >= 2:
                return True
    return False

def draw(x1,y1,x2,y2):
    for i in range(x1, x2 + 1):
        for j in range(y1, y2 + 1):
            visited[i][j] += 1

def overlapped(x1,y1,x2,y2, i,j,k,l):
    clear_board()   # 모두 0으로 리셋 
    draw(x1,y1,x2,y2)
    draw(i,j,k,l)
    return check_board()
    

# 첫번째 직사각형 (x1,y1,x2,y2)를 양 꼭지점으로 할때,
# 두번째 직사각형을 겹치지 않게 잡아 
# 최대 합을 반환하는 함수 
def find_max_sum_with_rect(x1,y1,x2,y2):
    max_sum = INT_MIN
    for i in range(n):
        for j in range(m):
            for k in range(i,n):
                for l in range(j,m):
                    # overlapped은 겹치면 True 
                    if not overlapped(x1,y1,x2,y2, i,j,k,l):
                        max_sum = max(max_sum, rect_sum(x1,y1,x2,y2)+rect_sum(i,j,k,l))
    return max_sum 

if __name__=="__main__":
    n,m=map(int, input().split())   # n*m 
    board = [list(map(int, input().split())) for _ in range(n)]
    visited = [[0]*m for _ in range(n)]
    INT_MIN = -sys.maxsize
    '''
    1. board에서 2 블록을 고른다. 
    2. 범위를 정한다.
    2.1 범위가 서로 안겹쳐야 한다
    3. 가장 값이 큰것을 저장한다. 
    '''
    
    max_sum = INT_MIN
    # (i,j)와 (k,l)을 양쪽 꼭지점으로 하는 첫번째 직사각형을 먼저 정하고 
    # 그 중 최댓값을 찾는다.
    for i in range(n):
        for j in range(m):
            for k in range(i,n):
                for l in range(j,m):
                    max_sum = max(max_sum, find_max_sum_with_rect(i,j,k,l))
            
    print(max_sum)