색칠 공부

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

색칠 공부 문제 풀이: 브루트포스 + 해시맵

1. 문제 요약

크기 H×W인 격자에서 일부 칸은 검정색이다. 이 격자에서 가능한 모든 3×3 부분 격자를 보면서, 그 안에 검정 칸이 정확히 i개인 격자의 개수를 구해야 한다. (단, 0 ≤ i ≤ 9)

2. 입력 조건 정리

• H, W: 격자 크기 (최대 10⁹)
• N: 검정 칸의 개수 (최대 10⁵)
• 다음 N개의 줄: 각각 검정 칸 좌표 (r, c)

3. 핵심 아이디어

전체 3×3 격자는 (H-2)×(W-2)개 존재하지만, H와 W가 너무 크기 때문에 전부 확인할 수는 없다.
다만, 검정 칸은 최대 10⁵개이므로 검정 칸이 포함된 3×3 격자만 추적해도 충분하다.

4. 단계별 구현

단계 1. 전체 3×3 격자의 개수

3×3 격자의 좌상단 좌표는 (1,1) ~ (H-2, W-2)까지 가능하다. 따라서 전체 격자 수는 다음과 같다.

total = (H - 2) * (W - 2)

단계 2. 각 검정 칸이 영향을 주는 격자 찾기

검정 칸 (r, c)는 다음 3×3 격자에 포함될 수 있다 (좌상단 기준):

(r-2, c-2) (r-2, c-1) (r-2, c)
(r-1, c-2) (r-1, c-1) (r-1, c)
(r,   c-2) (r,   c-1) (r,   c)

이 중 1 ≤ x ≤ H-2 그리고 1 ≤ y ≤ W-2인 좌표만 유효하다.

단계 3. 각 격자 내 검정 칸 개수 세기

각 검정 칸이 영향을 주는 모든 격자 좌표에 대해, 해당 격자 안의 검정 칸 개수를 딕셔너리에 저장한다.

cnt[(x, y)] = cnt.get((x, y), 0) + 1

단계 4. 개수별로 정리

cnt를 순회하며 검정 칸이 i개인 격자 개수를 셈한다. 이후, cnt에 없는 격자는 검정 칸이 0개인 격자이므로 전체 개수에서 빼서 계산한다.

5. 예제 추적 시각화

입력:
4 5 8
1 1
1 4
1 5
2 3
3 1
3 2
3 4
4 4

유효한 3×3 격자의 좌상단 좌표:

• (1,1), (1,2), (1,3)
• (2,1), (2,2), (2,3)

이 6개의 격자 중 검정 칸 개수는 다음과 같다:

좌상단 (x,y)	검정 칸 수
(1,1)	4
(1,2)	3
(1,3)	3
(2,1)	3
(2,2)	4
(2,3)	2

결과는 다음과 같다:

0
0
0
2
4
0
0
0
0
0

6. 전체 코드

import io
input = io.BufferedReader(io.FileIO(0), 1 << 18).readline

H, W, N = map(int, input().split())
black = [tuple(map(int, input().split())) for _ in range(N)]
cnt = {}

for r, c in black:
    for dx in (-2, -1, 0):
        x = r + dx
        if x < 1 or x > H - 2:
            continue
        for dy in (-2, -1, 0):
            y = c + dy
            if y < 1 or y > W - 2:
                continue
            cnt[(x, y)] = cnt.get((x, y), 0) + 1

ans = [0] * 10
for v in cnt.values():
    ans[v] += 1

total = (H - 2) * (W - 2)
ans[0] = total - len(cnt)

print('\n'.join(map(str, ans)))

7. 시간 및 공간 복잡도

• 시간 복잡도: O(N)
• 공간 복잡도: O(N)

8. 요약

• 전체 격자 수는 계산만 하고 직접 접근하지 않음
• 검정 칸이 들어가는 격자만 따로 추적
• 각 3×3 격자 안의 검정 칸 수를 해시맵으로 기록
• 해시맵에 없는 나머지 격자는 검정 칸 0개