[백준] 2563번_색종이

문제

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

---

코드

def solution(loc):
    arr = [[0] * 101 for _ in range(101)]
    answer = 0

    for (x, y) in loc:
        for i in range(x, x + 10):
            for j in range(y, y + 10):
                if arr[i][j] != 1:
                    arr[i][j] = 1
                    answer += 1
    print(answer)

# input
n = int(input())
loc = []

for _ in range(n):
    loc.append(tuple(map(int, input().split())))

solution(loc)

---

[생각의 흐름]

• 좌표를 2차원 배열로 바꿔서 해당 칸을 1로 색칠해 주면 되겠다.
• 좌표를 배열로 바꾸면 고려할 사항이 있나?
  첫번째 예시 (3, 7)을 고려해보자.
  [3, 7] ~ [3, 16],
  [4, 7] ~ [4, 16],
  .. ,
  [12, 7] ~ [12, 16]
  이렇게 채워진다.
• (100, 100) 좌표는 어떻게 표현될까?
  [101, 101]로 표현된다.
  -> 2차원 배열의 크기는 101x101로 만들어야겠다!

[설명]

• 101x101 크기의 2차원 배열 생성
  초기 값은 모두 0.
• 2중 반복문을 돌면서 [i][j]가 0인 경우에만 1로 바꿔주고 answer를 1 증가시킨다.

---

깨달음

[오류]

# 2차원 배열 생성
arr = [[0]*101] * 101

• 원인: shallow copy
• 설명:
  arr의 모든 행이 동일한 객체를 참조한다.
  예를 들어 행0, 행1, 행2, 행3을 생성했는데, 모두 행0의 값을 복사한게 아닌 주소값을 복사한 것이다.
  비록 행0, 행1, 행2가 따로따로 있지만,
  행0의 첫번째 값을 바꾸면 행1, 행2, 행3의 첫번째 값 또한 모두 변경되는 것이다.

[오류 수정]

# 2차원 배열 생성 
arr = [[0] * 101 for _ in range(101)]

• 반복문을 돌면서 직접 배열을 일일이 생성해주는 것이다.