백준 2563- 색종이

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

2563번: 색종이

 

이 문제는 색종이를 입력받아 전체 색종이의 넓이를 구하면 되는 문제이다.

처음에는 전체 색종이의 넓이에서 겹치는 부분을 빼도록 로직을 구현했는데

테스트 예제에서는 답이 잘 나왔지만 아마 겹치는 부분이 많은 경우를 포함시키지 못 해 오답처리 되는 것 같다.

일단 오류 코드는 다음과 같다.

def check(xy1, xy2): # 겹치는지 아닌지 체크해주는 함수
    x = [i for i in range(xy1[0][0], xy1[0][0]+11)]  # x 범위
    y = [i for i in range(xy1[0][1], xy1[0][1] + 11)]  # y 범위

    for i in xy2:
        if i[0] in x and i[1] in y:
            return 1

    return 0

def diff(xy1, xy2):  # 겹치는 부분의 넓이를 구해주는 함수
    x_d1 = max(xy1[0][0], xy2[0][0])
    x_d2 = min(xy1[0][0]+10, xy2[0][0]+10)
    y_d1 = max(xy1[0][1], xy2[0][1])
    y_d2 = min(xy1[0][1]+10, xy2[0][1]+10)
    result = (x_d2-x_d1)*(y_d2-y_d1)
    return result


n = int(input())
sq = []
xy = [] # 한 색종이의 4개의 꼭짓점을 담아둘 리스트
for i in range(n):
    x, y = list(map(int, input().split()))
    xy.append([x, y])
    xy.append([x, y+10])
    xy.append([x+10, y])
    xy.append([x+10, y+10])
    sq.append(xy)
    xy = []  # .clear() 사용시 -> sq 안이 빈 리스트로 바뀌어버림

flag = 0 # 겹치는 경우:1 / 겹치지 않는 경우 0
ans = 100 * n  # 하나도 겹치지 않을 경우, 전체 색종이의 넓이
flags = {}  # 중복 이슈를 방지하기 위해 만들어둔 딕셔너리
result1 =0
result2 = 0
for i in range(len(sq)-1):
    for j in range(i+1, len(sq)):
        flag = check(sq[i], sq[j]) # 겹치는 부분이 있는지 확인
        if flag == 1:  # 겹치는 부분이 있는 경우
            if i in flags.keys() and j in flags.keys(): # 이미 전에 겹치는 부분을 계산한 색종이일 경우
                flags[j].append(i)
                for k in flags[j]:
                    
                result1 = diff(sq[i], sq[flags[i]])
                result2 = diff(sq[j], sq[flags[j]])
                result = abs(result1-result2)  # 두 넓이의 차
            if i not in flags.keys():  # 전에 겹치는 부분이 없던 색종이일 경우
                flags[j] = [i]  # 겹치는 부분이 있는 색종이로 판정하고 어떠한 색종이와 겹쳤는지 딕셔너리 형태로 저장
                result = diff(sq[i], sq[j])
            ans -= result

print(ans)

 

이미 겹쳐진 색종이로 계산을 한 색종이의 경우, 전에 이미 차감했으므로 단순히 뺄 것이 아니라, 차이나는 부분만 전체 넓이에서 빼줘야한다. 

하나의 색종이가 다른 색종이들과 여러 번 겹쳐질 경우, 어떠한 색종이와 겹쳐졌었는지 딕셔너리에 리스트 형태로 계속 추가시킨 후 해당 색종이의 values에 다 접근하여 넓이를 비교 후, 더 큰 넓이가 계산되었을 경우 그 차이만큼 빼주고 아니면 그냥 넘기면 될 것 같은데 생각만해도 굉장히 복잡하다는 것을 알 수 있다.

그래서 구글링을 시도해보았고, 이차원 배열을 통해 굉장히 쉽게 문제 해결이 가능해 그 로직을 적용하였다.

 

이 문제의 조건을 보면, 도화지의 크기가 제한되어 있고 그 크기도 크지 않기 때문에 이차원 배열로 도화지를 그리고 그 안에서 색종이 영역만 칠한 후 그 색종이 영역의 갯수만 세면 넓이가 나온다.

키포인트는 색종이가 붙여진 영역은 중복될 수 있고, 중복이  되더라도 하나만 카운트가 되게끔 하면 된다.

 

구현)

1. 100*100의 이차원 배열 생성 후 0으로 초기화(어떠한 색종이도 없는 상태)

2. 색종이를 입력받아 10*10 영역에 1로 채우기

3. 전체 배열에서 1의 갯수 세기 == 전체 넓이

 

n = int(input())
p = [[0]*100 for i in range(100)]
result = 0
for i in range(n):
    a, b = list(map(int, input().split()))
    for j in range(10):
        for k in range(10):
            p[a+j][b+k] = 1

for i in p:
    result += i.count(1)

print(result)

아래 1을 세는 로직에서 단순히 p.count(1)을 해버리면 0이 나온다.

p의 원소들은 모두 100 크기의 리스트들로 구성되어있지 1로 구성되어 있는 것이 아니기 때문이다.

따라서, 반복문을 통해 리스트 한 줄에 접근하여 1의 갯수를 세어주면 된다.

 

느낀점)

문제를 있는 그대로 구현하려는 습관을 버리고 조금 더 원리적으로 쉽게 구현할 수 있는 방법을 계속해서 생각하는 연습을 해야겠다.

단순히 문제 난이도가 높다고 해서 구현하기 까다로운 것이 아니며, 원리를 이해하고 조금 더 쉽게 구현이 가능하도록 하는 데 시간이 걸릴 뿐이라는 것을 명심하자.