인공지능 개발일지

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

개발 지식/알고리즘

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

Prcnsi 2023. 2. 10. 21:37
728x90

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

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

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

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

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

 


문제

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

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

 

2563번: 색종이

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록

www.acmicpc.net

 

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

 

 

 

핵심 아이디어 

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

  • 겹치는 너비 계산을 따로 하지 않고 색종이가 있는 좌표에 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)

 


 

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

728x90