[python] 백준 2563번: 색종이

이번 문제는 어려운 문제는 아니었다..........

화가 좀 났을뿐............................

 

일단 이 문제를 풀기 위해서 세 가지의 방법을 생각했다.

1. 색종이를 한장씩 붙이고 그럴때 마다 겹친 것을 빼주는 방법

2. 색종이가 있는 평면의 끝에서 끝까지의 공간에서 빈 공간의 크기를 뚫어내는 방법

3. 전체 100*100을 2차원 배열로 주고, 색종이가 있는 칸을 색칠하는 방법

 

나는 세번째 방법을 선택했다.

첫번째 방법은 겹치는 모양이 매번 달라지고 두개가 겹쳐있는 그 사이에 새로운 색종이가 올라오면 상당히 힘들 것 같았고,

두번째 방법은 생각보다 괜찮은 방법이라고 생각했지만 세번째 방법이 좀 더 쉽고 재미있어 보여서 진행했다.

중간중간 아.. 시간 초과될거같다는 생각을 매우 많이 했지만 그래도 잘 해결되었다....^^

 

#이 코드는 틀린 코드입니다. 맞은 코드는 아래에 있습니다.
N=int(input())
field=[[0]*101]*101
for _ in range(N):
    a, b=map(int, input().split())
    for i in range(a, a+10):
        for j in range(b, b+10):
            field[i][j]=1
total=0
for i in range(101):
    total+=sum(field[i])
print(total)

 

생각은 정말 금방 했는데, 왜인지 자꾸 출력 값이 틀리게 나왔다.

한줄 한줄 뜯어 봐도 도대체 어떤 것이 문제인지 감이 안잡혀서 너무 화가 났다.

 

결국 답을 찾아냈는데, 정답은 배열의 선언 과정에 있었다....!!(절대 여기가 문제라고 생각 안했음)

파이썬에서 2차원 배열을 만드는 방법은 여러가지가 있는데,

for문으로 만들기, 곱하기 연산자 " * " 써서 만들어주기...등등 여러가지가 있다.

 

일단 곱하기 연산자가 너무 간단하기에 나는 당연히 곱하기 연산자를 썼다.

근데 여기서 문제였던 것이, 곱하기 연산자를 쓰면 배열이 "얕은 복사"를 하게 되어

같은 주소값을 복사하는 것이지 진짜 객체 자체를 복사하는 것이 아니었다....!

 

비슷한 예로 등호 연산자 " = "도 똑같이 주소값을 복사해서 얕은 복사를 한다.

 

이것을 해결하기 위해서는 아예 다른 새로운 객체로 만들어주어야하는데,

어떤 객체에 대해서 깊은 복사를 해야하는데, 이것은 copy 모듈 내에 deepcopy를 사용하면 된다고 한다.

 

하지만 일단 나는 2차원 배열을 선언하는 과정이었기 때문에 리스트 컴프리헨션을 사용하여 만들어주었다.

N=int(input())
field=[[0 for col in range(101)] for i in range(101)]
for _ in range(N):
    a, b=map(int, input().split())
    for i in range(a, a+10):
        for j in range(b, b+10):
            field[i][j]=1
total=0
for i in range(101):
    total+=sum(field[i])
print(total)

방법을 고민했던 시간보다 (틀려서)구현하는데에 시간을 너무 많이 썼지만

그래도 새로운 것을 배우게 된 좋은 계기라고 생각해서 아주 뿌듯하다.