[백준 2563번] 색종이 - 파이썬

백준 2d array 부분 색종이 알고리즘에 대해 풀어보겠습니다. (https://www.acmicpc.net/problem/2563)

 

 

처음 이 문제를 접했을 때 들었던 생각은

1. 각 색종이 area를 구하여 더함
2. 교집합 영역을 구함
3. 하나의 교집합 영역만 전체 area에 남겨두고, 나머지는 뺌

그런데 이렇게 처리하면 예외 케이스가 많이 생겨 너무 복잡도가 증가한다는 단점이 있었습니다.

 

단순하게 생각해보면, A라는 100 x 100 매트릭스가 있다고 가정했을때,

겹치든 겹치지지 않든, 색종이가 영역을 덮고 있다면 A[i][j] 의 값을 1로 설정하고 그렇지 않다면 0으로 설정하면 불필요한 예외 처리 없이 문제를 해결 할 수 있습니다.

 

정답 코드는 다음과 같습니다.

 

if __name__ == '__main__':
    n = int(input())
    arr = [[0] * 100 for _ in range(100)]  # 0 initialization

    for _ in range(n):
        x, y = map(int, input().split())

        for i in range(x, x + 10):
            for j in range(y, y + 10):
                arr[i][j] = 1

    total = 0
    for k in range(100):
        total += arr[k].count(1)

    print(total)

 

1. A라는 100 x 100 2d array 생성 
2. n만큼 input을 반복해서 받고
3. 각 input 마다 가로변과 세로변의 값을 구해서 A의 요소의 값을 할당
4. 색종이 영역에 관련된 첫번째 반복문이 모두 끝나면, 전체 area를 구함 (count 활용)