21862. 사각형 그리기 게임

https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AZTSyabKcE7HBINJ&contestProbId=AZFYm0OKCpEDFAVs&probBoxId=AZTYhdtaJTnHBIOK&type=USER&problemBoxTitle=99.+IM+%EB%8C%80%EB%B9%84+%EB%AC%B8%EC%A0%9C&problemBoxCnt=11

SW Expert Academy

 

1️⃣ 문제 개요

• N × N 크기의 정수 배열이 주어짐.
• 같은 숫자로 이루어진 가장 큰 직사각형을 찾고, 해당 직사각형의 개수를 계산해야 함.

---

2️⃣ 코드 설명

import sys
sys.stdin = open('Solve.txt')
input = sys.stdin.readline

T = int(input())

for t in range(1, T+1):
    N = int(input())
    board = [list(map(int, input().split())) for _ in range(N)]
    max_Area = 0
    count = 0

    # 최대 직사각형의 넓이 찾기
    for y in range(N):
        for x in range(N):
            for dy in range(0, N-y):
                for dx in range(0, N-x):
                    if board[y][x] == board[y+dy][x+dx]:
                        Area = (dy+1) * (dx+1)
                        if Area > max_Area:
                            max_Area = Area

    # 최대 넓이를 가진 직사각형 개수 세기
    for y in range(N):
        for x in range(N):
            for dy in range(0, N-y):
                for dx in range(0, N-x):
                    if board[y][x] == board[y+dy][x+dx]:
                        Area = (dy+1) * (dx+1)
                        if Area == max_Area:
                            count += 1

    print(f'#{t}', count)

---

3️⃣ 코드 동작 과정

1. 입력 처리
   • 여러 개의 테스트 케이스를 처리하기 위해 T를 입력받음.
   • N × N 크기의 배열을 입력받아 board 리스트에 저장.
2. 최대 면적 찾기
   • (y, x) 위치에서 시작하여 가능한 모든 (dy, dx) 크기의 직사각형을 탐색.
   • 직사각형의 대각선 (y+dy, x+dx) 위치의 값이 동일한 경우만 면적을 계산하여 max_Area 갱신.
3. 최대 면적을 가진 직사각형 개수 세기
   • 다시 같은 방식으로 탐색하며 max_Area와 동일한 면적을 가지는 직사각형을 세어 count 변수에 저장.
4. 부분집합 탐색과의 연관성
   • 이 문제의 접근 방식은 부분집합을 생성하는 방법과 유사합니다.
   • (y, x)에서 시작하는 모든 가능한 직사각형의 조합을 탐색하므로, 완전 탐색을 통한 부분집합 탐색 기법이 적용됨.
   • 부분집합 탐색은 모든 경우를 고려하는 방식이며, 이 문제에서는 모든 직사각형의 가능성을 탐색하는 점에서 유사함.

---

4️⃣ 이 문제를 풀기 위해 반드시 알아야 할 개념

• 브루트 포스(완전 탐색): 모든 가능한 경우를 하나하나 탐색하는 기법.
• 2차원 배열 탐색: for 문을 중첩하여 행렬을 순회하는 방법.
• 중첩 반복문: 가능한 모든 직사각형을 찾기 위해 4중 반복문을 사용.
• 부분집합 탐색(Subset Search): 가능한 모든 선택을 고려하는 방식으로, 이 문제에서 직사각형 탐색과 유사하게 적용됨.
• 조건문 활용: 특정 조건 (board[y][x] == board[y+dy][x+dx])을 만족하는 경우만 진행.

📌 이 코드는 완전 탐색 방식이므로 O(N^4)의 시간 복잡도를 가집니다. N이 클 경우 더 효율적인 알고리즘이 필요할 수 있습니다.