Baekjoon 백준 알고리즘 - 색종이( 2563 )

1. 문제 소개

• 실버 수준 구현 문제다.
• https://www.acmicpc.net/problem/2563

 

2. 코드

def set_test_case():
    T = int(input())
    rectangles = []
    for i in range(T):
        in_temp = input().split(" ")
        r = [int(in_temp[0]),int(in_temp[1])]
        rectangles.append(r)

    return rectangles

def solution():
    size = 10
    max_size = 100
    area = 0

    matrix = [[0 for i in range(max_size)] for j in range(max_size)]
    rectangles= set_test_case()

    # 색종이 영역 마킹
    for rectangle in rectangles:
        for j in range(rectangle[0],rectangle[0]+size):
            for k in range(rectangle[1],rectangle[1]+size):
                matrix[j][k] = 1

    # 색종이 영역 완전 탐색 = 배열 요소 1은 1X1 의 넓이로 본다.
    for i in range(max_size):
        for j in range(max_size):
            if matrix[i][j] == 1:
                area+=1

    print(area)

if __name__ == '__main__':
    solution()

3. 코멘트

• 처음에는 색종이의 꼭지점 좌표를 이용해, 겹치는 영역 또는 빈 영역이 발생할 수 있는 경우의 룰(특징)을 정의해서 사각형을 계산해 답을 도출 하는 방법으로 고민했다. ( CCW, 컨벡스헐 알고리즘을 적용해서 풀 수 있다는 피드백) 
• 내가 생각한 방식은 꽤 복잡하고, 주어진 조건(도화지 크기, 색종이 수 제한) 과 1초라는 제한 시간은 완전 탐색 방식으로 푸는게 간단하다는 스터디원의 풀이를 보고 나도 다시 풀었다. 
• 방법은 간단하게 도화지 크기 (100 * 100)의 2차원 배열을 만들고, 색종이의 영역 만큼 마킹을 한 후 마킹된 원소를 넓이로 보고 답을 출력한다.
• 오랜만에 알고리즘 스터디를 해서 너무 재밌었다. 생업 때문에 자주는 아니더라도 꾸준히 모였으면 좋겠다.
• 이 글을 보고 알고리즘 스터디에 관심이 있는 분들은 언제든지 연락을... :)