[백준, python] 백준 2563 색종이 - (2차원 배열로 겹치는 색종이의 넓이 구하기)

안녕하세요! 저는 요즘 알고리즘 공부도 열심히 하고,

이번달에 말도 안 되게 일이 많이 들어와서 열심히 하고 있습니다,,

계속 느끼는 거지만 시간 관리를 잘하는 게 정말 정말 중요한 것 같습니다.

시간이 금이다를 느끼고 있는 요즘이네요 ㅎㅎ

그럼 각설하고 풀이 들어갑니다.

 

---

문제

오늘 풀 문제는 2563번 색종이 문제로 가로가 100, 세로가 100 크기의 2차원 좌표에서, 입력한 개수 N만큼의 색종이의 시작 좌표가 주어지고 모든 색종이는 가로, 세로가 10의 크기라고 가정할 때, 이 색종이 너비의 합을 구하는 문제이다. 

https://www.acmicpc.net/problem/2563

2563번: 색종이

 

자세한 풀이를 하기 전에 여기서 배운 핵심부터 정리하고 넘어가겠습니다.

 

 

 

핵심 아이디어 

핵심 아이디어는 아래와 같습니다. 

• 겹치는 너비 계산을 따로 하지 않고 색종이가 있는 좌표에 1을 처리해서 1의 합으로 너비를 구함
• x, y 축의 최대 범위가 주어진 2차원 좌표를 기반으로 하는 문제
• x, y축의 각 점을 2차원 배열로 표현(구현)!!
• x, y 축 최대 범위의 값을 모두 0으로 초기화해서 생성
  • [[0 for _ in range(101)] for _ in range(101)]
• 입력받은 범위만큼 각 색종이 넓이에 해당하는 좌표를 반복문을 돌며 범위의 값을 1로 처리 
• 모든 반복문을 끝내면, 중복되는 값의 좌표도 모두 1로 처리되므로 전체 배열에서 1의 개수를 세면 넓이가 됨. \

저는 처음에 이 문제를 풀 때 어떻게 푸려고 했냐면, 그냥 생각나는 대로 겹치는 색종이의 "넓이"에 집중해서, 조건문을 매우 길게 작성해서 각 케이스마다 모든 넓이를 더하고, 겹치는 부분을 빼려고 했지만 더 효율적인 방법이 있었다.

바로 "2차원 배열을 사용해서 각 점의 좌표에 넓이가 있으면 1, 없으면 0으로 처리해서", 각 자리의 좌표를 배열로 표현하여 하나의 좌표에 넓이가 있으면 1로 처리하는 게 인상적이었다.

 

그래서 이번에도 마찬가지로 가장 중요한 아이디어는 뭐다? 앞으로 2차원 공간에 어떤 너비를 구하는 문제가 나오면 2차원 배열을 만들어서 각 좌표를 0으로 표시하고, 그 좌표를 지나면 1로 있다고 처리해서, 총넓이를 구하는 게 아주 효율적이다. 

 

 

알고리즘 동작 예시

예를 들어서 아래와 같은 5x5(가로 x 세로) 크기의 좌표에서 색종이의 너비가 2라고 가정할 때,

입력으로 색종이 하나에 색종이 시작 위치가, x는 2, y는 2가 나왔다면 아래와 같이 2,2를 시작으로 2의 범위만큼 x는 2,3까지 두 칸, y축도 2,3까지 두 칸 해서 반복문으로 x, y의 범위만큼 반복을 하며, 해당 좌표에 1의 값을 할당해 주면 최종적으로 아래와 같이 배열이 채워지게 된다. 그리고 이 배열에서 1의 개수를 세면 이 좌표에서 사각형의 넓이가 된다!

그래서 최종적으로 이 배열에서 1의 개수를 세면 모든 사각형의 넓이를 구할 수 있다. 이 방법을 사용하면 색종이가 여러 개 있어 겹치는 부분이 있어도, 같은 영역에 1을 처리하고, 1의 개수를 세는 것이므로 중복 없이 카운팅 할 수 있다.

 

구현 코드

아래는 구현 코드이다. 여기서 2차원 리스트를 만드는 부분만 집중해서 보면 될 것 같다.

N=int(input())
arr=[[0 for _ in range(101)] for _ in range(101)]

for _ in range(N):
    # x,y d입력 받기
    x,y=map(int, input().split())
    for i in range(x,x+10):
        for j in range(y,y+10):
            # print('좌표',i,j)
            arr[i][j]=1

area=0
for _ in range(100):
    # print(arr[_].count(1))
    area+=arr[_].count(1)
print(area)

 

---

 

그럼 오늘도 읽어 주셔서 감사합니다:)