들어가기 앞서, 문제를 이해하는 것이 얼마나 중요한지 다시 한 번 깨닫게 되는 문제였습니다. 이 문제를 풀면서 헷갈리고 방향을 잘못 잡았다는 점을 리뷰하고자 글을 작성하였습니다.
Challenge
문제를 요약하면, 정해진 넓이(도화지)내의 색종이를 여러장 받아서 놓고, 전체 넓이를 구하는 문제입니다.
•
N개의 좌표가 주어집니다.
•
좌표에서부터 10 x 10의 종이가 있고, 그 종이는 절대 도화지 밖으로 벗어나지 않습니다.
•
종이는 겹칠 수 있고, 여러 개가 동시에 겹칠 수도 있습니다.
Description
가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.
예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.
Inputs
첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다.
색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다.
색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다
* Examples 1
3
3 7
15 7
5 2
Plain Text
복사
Outputs
첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.
* Examples 1
260
Plain Text
복사
Solve
문제 풀이로 요구하는 내용은, N개의 색종이가 주어지고 100 x 100의 도화지에 올라가 덮어진 전체 색종이 넓이를 구하는 것입니다.
Issues
처음에 문제를 풀 때, 내용을 잘못 이해하고 있었던 점이 있습니다. 색종이가 겹치는 부분에 대해서만 집중하고 전체적인 문제 내용을 파악하지 못했었습니다. 때문에 다음과 같은 알고리즘이 나오게 됐습니다.
Failed
아래의 풀이에서 사용한 알고리즘은 두 개의 사각형이 겹쳤을 때 겹치는 영역에 대한 정보를 계산하는 방법을 적용해보았습니다. 다만 이 방법을 적용하고자 할 때, 몇 번이고 겹칠 수 있기 때문에 while문을 통해 더이상 겹치는 영역이 없는지 확인하여 계산을 끝내는 방식입니다.
1.
전체 사각형의 넓이를 더하고
2.
겹치는 부분의 x, y, w, h 정보를 통해 중복되어 겹치는 부분을 저장합니다.
3.
홀수 번째로 검사한 겹치는 부분의 넓이는 빼고, 짝수 번째로 검사한 겹치는 부분의 넓이는 더해줍니다.
4.
더 이상 겹치는 부분이 없을 때까지 2번~ 3번 과정을 반복합니다.
5.
결과를 출력합니다.
이와 같은 방법은 중복된 겹치는 부분은 제외하고, 전체 겹치는 넓이를 계산하는 방법으로 알고리즘을 계산하였습니다. 단, 이렇게 구현할 경우, 겹치는 부분이 얼마나 있을지 알 수 없기 때문에 계산식이 매우 오래걸릴 수 있습니다. 색종이의 수가 100개이고 최대 회수로 겹치는 영역이 있다면, 최대 100!(팩토리얼) 회수 만큼 계산이 필요할 것으로 보입니다. 따라서 해당 알고리즘으로는 풀이가 불가능하였습니다.
import sys
import itertools
N = int(sys.stdin.readline().strip())
done = False
width, height = 10, 10
rectangles = []
answer = (width*height)*N
repeated = 1
def get_intersection_area(r1, r2):
# x: 0, y: 1, w: 2, h: 3
if r1[0] > r2[0] + r2[2]:
return None, 0
elif r1[0] + r2[2] < r2[0]:
return None, 0
elif r1[1] > r2[1] + r2[3]:
return None, 0
elif r1[1] + r1[3] < r2[1]:
return None, 0
x = max(r1[0], r2[0])
y = max(r1[1], r2[1])
w = min(r1[0] + r1[2], r2[0] + r2[2]) - x
h = min(r1[1] + r1[3], r2[1] + r2[3]) - y
return [(x, y, w, h), w*h]
for __ in range(N):
# x, y, w, h
rectangles.append([int(i) for i in sys.stdin.readline().strip().split(" ")] + [width, height])
if N == 1:
print(width * height)
else:
while not done:
_tmp = []
if len(rectangles) <= 1:
done = True
break
for r1, r2 in itertools.combinations(rectangles, 2):
rect, area = get_intersection_area(r1, r2)
if not rect:
continue
if repeated % 2:
answer -= area
else:
answer += area
_tmp.append(rect)
rectangles = _tmp
print(answer)
Python
복사
Success
아래의 알고리즘은 100 x 100의 영역을 2차원 배열로 설정하고, 각 좌표별로 1을 세팅하는 방법으로 구현하였습니다. 해당 방법으로 구현할 경우, 겹치는 부분에 1로 다시 한 번 덮어씌우더라도 넓이 계산에 중복이 없다는 점을 이용하였습니다. 이러한 조건이 가능한 이유로는 100 x 100의 영역이라는 조건이 있기 때문에 가능한 것이라고 생각됩니다.
import sys
# Initialization
w, h = 10, 10
paper = []
for __ in range(100):
paper.append([0 for __ in range(100)])
# Solve
N = int(sys.stdin.readline().strip())
for __ in range(N):
x, y = [int(i) for i in sys.stdin.readline().strip().split(" ")]
for _w in range(w):
for _h in range(h):
paper[x+_w-1][_h+y-1] = 1
total = 0
for p in paper:
# print(" ".join([str(_p) for _p in p]))
total += sum(p)
print(total)
Python
복사
Reviews
문제를 풀 때 알고리즘을 구현하는 것에 급급할 것이 아니라 문제를 인지하고 어떠한 방법으로 푸는 것이 좋은지 적절한 연구가 필요하다는 것을 다시 한 번 깨닫게 되었습니다. 무엇보다 문제를 정확하게 파악하는 것만큼 중요한 것은 없다는 점을 뼈저리게 느꼈습니다. 실패한 알고리즘을 설계할 때 100 x 100 도화지에 대한 조건을 중요하게 생각하지 않아 문제를 잘못된 방향으로 풀고자 하고, 그 만큼 시간을 많이 소요하게 되었습니다.
