[백준/파이썬] 1186번 직사각형 색칠하기 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 1186번 직사각형 색칠하기
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
2차원 평면에 축에 평행한 직사각형 N개가 있다. 이 중 K개를 칠할 것이다.
색칠한 면적 중 보이는 것의 최댓값을 구하는 프로그램을 작성하시오.
- 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요
코드
class Square:
l=b=r=t=0
def __init__(self,l,b,r,t): self.l,self.b,self.r,self.t=l,b,r,t
def __str__(self):return f'Square(l:{self.l}, b:{self.b}, r:{self.r}, t:{self.t})'
def area(self): return (self.r-self.l)*(self.t-self.b)
def stack(self, other):
# self가 other의 꼭짓점 0개 포함 - 안겹치는 경우
if self.l >= other.r or\
self.b >= other.t or\
self.r <= other.l or\
self.t <= other.b:
return [self]
# self가 other의 꼭짓점 0개 포함 - self가 other에 포함
elif self.l >= other.l and\
self.b >= other.b and\
self.r <= other.r and\
self.t <= other.t:
return []
# self가 other의 꼭짓점 0개 포함 - self가 other에 의해 작은 하나로 잘림
# other이 왼쪽
elif self.l >= other.l and\
self.l <= other.r <= self.r and\
self.b >= other.b and\
self.t <= other.t:
return [Square(other.r, self.b, self.r, self.t)]
# other이 아랫쪽
elif self.b >= other.b and\
self.b <= other.t <= self.t and\
self.l >= other.l and\
self.r <= other.r:
return [Square(self.l, other.t, self.r, self.t)]
# other이 오른쪽
elif self.r <= other.r and\
self.l <= other.l <= self.r and\
self.b >= other.b and\
self.t <= other.t:
return [Square(self.l, self.b, other.l, self.t)]
# other이 위쪽
elif self.t <= other.t and\
self.b <= other.b <= self.t and\
self.l >= other.l and\
self.r <= other.r:
return [Square(self.l, self.b, self.r, other.b)]
# self가 other의 꼭짓점 0개 포함 - self가 other에 의해 작은 둘로 잘림
# self가 other에 비해 가로로 긴 경우
elif self.l <= other.l <= other.r <= self.r and\
self.b >= other.b and\
self.t <= other.t:
return [Square(self.l, self.b, other.l, self.t),
Square(other.r, self.b, self.r, self.t)]
# self가 other에 비해 세로로 긴 경우
elif self.b <= other.b <= other.t <= self.t and\
self.l >= other.l and\
self.r <= other.r:
return [Square(self.l, other.t, self.r, self.t),
Square(self.l, self.b, self.r, other.b)]
# self가 other의 꼭짓점 4개 포함
elif self.l <= other.l and\
self.b <= other.b and\
self.r >= other.r and\
self.t >= other.t:
return [Square(self.l, other.t, self.r, self.t),
Square(self.l, other.b, other.l, other.t),
Square(other.r, other.b, self.r, other.t),
Square(self.l, self.b, self.r, other.b)]
else:
# self 내부에 other의 좌상단이 포함
lt = self.l <= other.l <= self.r and\
self.b <= other.t <= self.t
# self 내부에 other의 우상단이 포함
rt = self.l <= other.r <= self.r and\
self.b <= other.t <= self.t
# self 내부에 other의 우하단이 포함
rb = self.l <= other.r <= self.r and\
self.b <= other.b <= self.t
# self 내부에 other의 좌하단이 포함
lb = self.l <= other.l <= self.r and\
self.b <= other.b <= self.t
if lt:
# 좌상단과 우상단이 포함
if rt:
return [Square(self.l, self.b, other.l, other.t),
Square(other.r, self.b, self.r, other.t),
Square(self.l, other.t, self.r, self.t)]
# 좌상단과 좌하단이 포함
elif lb:
return [Square(self.l, other.t, self.r, self.t),
Square(self.l, other.b, other.l, other.t),
Square(self.l, self.b, self.r, other.b)]
# 좌상단만 포함
else:
return [Square(self.l, self.b, other.l, self.t),
Square(other.l, other.t, self.r, self.t)]
elif rt:
# 우상단과 우하단이 포함
if rb:
return [Square(self.l, other.t, self.r, self.t),
Square(other.r, other.b, self.r, other.t),
Square(self.l, self.b, self.r, other.b)]
# 우상단만 포함
else:
return [Square(self.l, other.t, other.r, self.t),
Square(other.r, self.b, self.r, self.t)]
elif rb:
# 우하단과 좌하단이 포함
if lb:
return [Square(self.l, other.b, other.l, self.t),
Square(other.r, other.b, self.r, self.t),
Square(self.l, self.b, self.r, other.b)]
# 우하단만 포함
else:
return [Square(self.l, self.b, other.r, other.b),
Square(other.r, self.b, self.r, self.t)]
elif lb:
# 좌하단만 포함
return [Square(self.l, self.b, other.l, self.t),
Square(other.l, self.b, self.r, other.b)]
n,k=map(int,input().split())
l=[]
for _ in range(n):
newSquare = Square(*map(int,input().split()))
for i in range(len(l)):
tmp = []
for j in range(len(l[i])):
tmp+=l[i][j].stack(newSquare)
l[i]=tmp
l.append([newSquare])
size = []
for i in range(n):
#print(*map(str,l[i]))
size.append((sum(map(lambda square:square.area(),l[i])),i+1))
size.sort(key=lambda x:(-x[0],x[1]))
size=list(map(lambda x:x[1],size[:k]))
size.sort()
print(*size)
설명
문제의 난이도에 비해 풀이과정이 상당히 긴 문제입니다.
제가 상당히 비효율적으로 비교를 한 감이 있지만, 어쨌든 이 방식으로 풀었으므로 이 풀이를 설명드리겠습니다.
위 그림은 두 사각형이 겹치는 경우를 나타낸 것입니다.
각 경우에 대해서 조건문으로 하나하나 비교하여(…) 두 사각형(이미 입력받은 사각형과 새로 입력받은 사각형)의 겹치는 관계를 파악합니다. 이후, 기존 사각형의 안겹친 부분을 잘라내어 새로운 사각형으로 등록합니다. 이때, 잘라진 사각형들이 모두 하나의 사각형으로 인식될 수 있도록 같은 리스트에 들어있게 하기 위해 l을 2차원 리스트로 사용합니다.
이 과정을 마지막 사각형을 입력받을 때 까지 반복 후, 각 사각형들의 넓이를 구해줍니다. 이때, 각 사각형은 잘린 사각형들로 구성되어 있을 것이므로 해당 잘린 사각형들의 넓이 합을 넓이로 사용합니다.
순번을 기억하기 위해 넓이와 입력받은 순번 정보를 갖는 튜플 리스트를 생성, 넓이를 1순위 기준, 순번을 2순위 기준으로 정렬해줍니다. 이때, 넓이에 관해서는 내림차순, 순번에 관해서는 오름차순으로 합니다.
이후, k개의 사각형만 칠할 수 있으므로 인덱스가 k인 사각형부터는 버립니다. 다시 사각형을 번호순대로 출력해주어야 하므로, 순번 정보만 남은 리스트를 만들고, 그 리스트를 정렬하여 요소들을 모두 출력해주면 됩니다.
__str__ 함수는 디버깅을 위해 구현한 함수로, 굳이 구현하실 필요는 없습니다.
댓글남기기