[백준/Python] 2563 - 색종이

문제

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다. 이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 색종이가 붙은 검은 영역의 넓이를 구하는 프로그램을 작성하시오.

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 그림과 같은 모양으로 붙였다면 검은색 영역의 넓이는 260이 된다.

입력

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다. 색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다. 색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다

출력

첫째 줄에 색종이가 붙은 검은 영역의 넓이를 출력한다.

풀이

설계

2차원 리스트를 활용한 문제이므로 인덱싱을 통해 색종이가 덮이는 지점에 해당하는 요소들의 값을 특정한 값으로 바꿔준 후 해당 값을 모두 세는 것으로 해결한다. 정리하면 다음과 같다.
1. 100 * 100의 행렬을 만든다.
2. 첫 번째 값이 '열' 인덱스 값이므로 그 값부터 +10까지를 슬라이싱하여 값을 "*"로 바꾼다.
3. 두 번째 값이 '행' 인덱스 값의 마지막 값이므로 그 값부터 -11을 한 값을 슬라이싱하여 값을 "*"로 바꾼다.
4. 배열을 1차원으로 바꾼 후 전체 배열에서 "*"의 값을 세어 반환한다.

코드

# 100 * 100 크기의 0으로 이루어진 2차원 배열을 생성
mat = [[0 for _ in range(101)]for _ in range(101)]

n = int(input())

for _ in range(n):
	# '열' 인덱스 시작 값과 '행' 인덱스 값의 마지막 값을 각각 저장
    # 이때, '행' 인덱스 값은 100에서 빼 줌으로써 마지막 값으로 지정
    column, row = map(int, input().split())
    row = len(mat) - row - 1
    
    # 행렬을 순회하며 10 * 10 크기만큼의 값을 "*"로 변경
    for i in range(10):
        for j in range(10):
            mat[row-j][column+i] = "*"

# 2차원 행렬을 1차원 배열로 변환한 뒤 count()로 "*"의 개수를 반환
print(sum(mat, []).count("*"))

특기 사항

1. 풀이 시 '위아래'가 바뀌어도 문제의 해결에는 지장이 없다(면적을 구하는 것이기 때문에). 즉, '행'의 값에 대하여 나처럼 1~10까지를 빼는 것이 아니라 더해서 계산해도 무방하다. 다만 나는 차후 실제 위치가 중요한 문제가 있을 수도 있으므로 위아래를 굳이 구별하여 구현한 것.

2. 행렬을 구현하고 값을 바꾸는 것은 금방 해결하였으나 예상치 못한 곳에서 문제가 있었는데, 바로 최초 100*100의 행렬을 만드는 부분. 이전까지 특정 값으로 채워진 n * m 크기의 행렬을 만들 때 '[[0] * m] * n'과 같은 형태로 만들었는데, 이 경우 하나의 행에 대해서 값을 변경하려고 해도 모든 행의 값이 동일하게 변경된다. 무슨 말이냐면,

# 배열 생성
arr_1 = [[0] * 5] * 5

# 인덱싱하여 값 변경
arr_1[0][1] = "1"
arr_1

이렇게 하면 1번째 행의 2번째 열만 1로 바뀌어야 하지만 실제 값은 다음과 같다.

[[0, '1', 0, 0, 0],
 [0, '1', 0, 0, 0],
 [0, '1', 0, 0, 0],
 [0, '1', 0, 0, 0],
 [0, '1', 0, 0, 0]]

배열을 생성할 때 첫 번째 행을 생성한 후 그것을 단순히 곱하여 나타냄으로써 사실상 동일한 메모리 공간을 사용하게 된다...고 생각된다. 자세한 건 공부해봐야 할 듯.

따라서 단순히 곱하는 것이 아니라 nested list를 활용하는 식으로 배열을 생성해야 한다.

# 배열 생성
arr_2 = [[0 for _ in range(5)] for _ in range(5)]

# 값 변경
arr_2[0][1] = '1'
arr_2

[[0, '1', 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0]]

배열 생성 방식만으로도 결과가 완전히 달라진다. 2차원 행렬의 구현을 활용한 문제는 상당히 많이 나타나기 때문에 이런 세세한 부분들을 기억해 둘 필요가 있을 듯. 메모리 등 CS 부분도 어느 정도 알아 두어야 하겠다.