๋ฌธ์
https://www.acmicpc.net/problem/2630
๋ฐฑ์ค ๋จ๊ณ๋ณ ํ์ด - ๋ถํ ์ ๋ณต
ํ์ด
์ ์ฒด ์ฝ๋
# ๋ถํ ์ ๋ณต
# ๋ฉ๋ชจ๋ฆฌ: 31120KB / ์๊ฐ: 52ms
# 1
from sys import stdin
input = stdin.readline
N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]
ret = [0, 0]
# 2
def quadtree(row: int, col: int, size: int) -> None:
color: int = paper[row][col]
for i in range(row, row+size):
for j in range(col, col+size):
if paper[i][j] != color:
half = size // 2
# ์ข์, ์ขํ, ์ฐ์, ์ฐํ ์์๋๋ก ์ฌ๊ท
quadtree(row, col, half)
quadtree(row+half, col, half)
quadtree(row, col+half, half)
quadtree(row+half, col+half, half)
return
ret[color] += 1 # ๋ชจ๋ ์์ด ๊ฐ๋ค๋ฉด ํด๋น ์๊น ๊ฒฐ๊ณผ๊ฐ(0๋๋ 1)์ 1 ์ถ๊ฐ
# 3
quadtree(0, 0, N)
print(f"{ret[0]}\n{ret[1]}")
๋จ๊ณ๋ณ ํ์ด
1. ์ ๋ ฅ๊ฐ ํ ๋น
from sys import stdin
input = stdin.readline
N = int(input())
paper = [list(map(int, input().split())) for _ in range(N)]
ret = [0, 0]
N: ์ ๋ ฅ์ค์ ๊ฐฏ์(=ํ ๊ฐฏ์)paper: ์ ๋ ฅ ๋ฐฐ์ด๊ฐ์ ์ ์ฅํ 2์ฐจ์ ๋ฆฌ์คํธ.- ํ๋งํผ ์ํํ๋ฉฐ ๊ฐ ์ค์ ์ ๋ ฅ๊ฐ์ ์ ์ํ์ผ๋ก ๋ณํ ํ ๋ฆฌ์คํธ๋ก ๋ง๋ค์ด์ค๋ค.
[[0๋ฒ์งธ ํ์ ์์๋ค], [1๋ฒ์งธ ํ์ ์์๋ค]...]
ret = [0, 0]: ๊ฒฐ๊ณผ๊ฐ์ ์ ์ฅํ ๋ฆฌ์คํธ. 0๋ฒ์งธ ์ธ๋ฑ์ค๋ ํฐ์, 1๋ฒ์งธ ์ธ๋ฑ์ค๋ ํ๋์๊ฐ์ ์ ์ฅ.
2. ์ฟผ๋ํธ๋ฆฌ ํจ์ ์์ฑ
def quadtree(row: int, col: int, size: int) -> None:
color: int = paper[row][col]
for i in range(row, row+size):
for j in range(col, col+size):
if paper[i][j] != color:
half = size // 2
# ์ข์, ์ขํ, ์ฐ์, ์ฐํ ์์๋๋ก ์ฌ๊ท
quadtree(row, col, half)
quadtree(row+half, col, half)
quadtree(row, col+half, half)
quadtree(row+half, col+half, half)
return
ret[color] += 1 # ๋ชจ๋ ์์ด ๊ฐ๋ค๋ฉด ํด๋น ์๊น ๊ฒฐ๊ณผ๊ฐ(0๋๋ 1)์ 1 ์ถ๊ฐ
- ์ฌ๊ทํํ๋ก ์์ฑ
row: ํ,col: ์ด,size: ์์ข ์ด์ ํฌ๊ธฐcolor: ๋น๊ตํ๋ฉฐ ๊ฒ์ฌํ ๊ธฐ๋ณธ๊ฐ. ๊ฒ์ฌํ ๋ถ๋ถ์ ์ ์ผ ์ฒซ๋ฒ์งธ ๊ฐ์ผ๋ก ํ ๋น.- ์ฃผ์ด์ง ํ/์ด๊ฐ๋ถํฐ ํ+ํฌ๊ธฐ/์ด+ํฌ๊ธฐ ๊ฐ๊น์ง ์ํํ๋ฉฐ ์ฒดํฌํ๋ค.
- ๋ง์ฝ, ํ์ฌ ๊ฐ
์์ข ์ด[i][j]์ด ๊ธฐ๋ณธ๊ฐcolor๊ณผ ๋ค๋ฅด๋ค๋ฉด, half: ์ฃผ์ด์ง ์ฌ์ด์ฆ๋ฅผ ๋ฐ์ผ๋ก ๋๋๊ฐ, ์ฆ 4๋ฑ๋ถํ ์์ข ์ด์ ํ ๋ณ์ ๊ธธ์ด- ์ผ์ชฝ ์/์๋, ์ค๋ฅธ์ชฝ ์/์๋ ์์๋ก ์ฌ๊ทํธ์ถ์ ์ค์ํ๋ค.
- ํธ์ถ์ ๋ง์น๋ฉด
return์ผ๋ก ํจ์๋ฅผ ์ข ๋ฃ
- ๋ง์ฝ, ํ์ฌ ๊ฐ
- ๋ชจ๋ ๊ฐ์ด ๊ฐ๋ค๋ฉด
ret[color]๊ฐ์ 1์ ๋ํด์ค๋ค.- ํฐ์์ 0, ํ๋์์ 1๋ก ์ฃผ์ด์ง๋ฏ๋ก
color๊ฐ์ด 1์ด๋ผ๋ฉดret[0, 1], 0์ด๋ผ๋ฉดret[1, 0]์ด ๋๋ค.
- ํฐ์์ 0, ํ๋์์ 1๋ก ์ฃผ์ด์ง๋ฏ๋ก
3. ํจ์ ํธ์ถ ๋ฐ ๊ฒฐ๊ณผ๊ฐ ์ถ๋ ฅ
quadtree(0, 0, N)
print(f"{ret[0]}\n{ret[1]}")
0, 0, N์ ์ธ์๊ฐ์ผ๋ก ๋ฃ์ด ํจ์๋ฅผ ํธ์ถํ๋ค.- ํฐ์, ํ๋์ ์์๋๋ก ํ์ค์ฉ ์ถ๋ ฅํ๋ผ๊ณ ํ์ผ๋ฏ๋ก
ret[0],ret[1]์ ์ฐจ๋ก๋๋ก ์ถ๋ ฅ.