우주의 평화를 위하여

1. 문제

지구를 호시탐탐노리는 아주 질나쁜 외계인들을 다 무찔러야한다. 그러기 위해서는 외계인들의 행성인 A행성의 모든 기계들을 파괴시켜야한다.

 

1. A 행성에 있는 모든 기계의 위치는 N x N크기의 격자판 상에 나타낼 수 있다.
2. 격자판 위의 모든 기계가 같은 종류의 기계라면 단 한 번의 공격으로 모든 기계를 파괴할 수 있다.
3. 만약 격자판 위의 기계들 중 하나라도 다른 종류의 기계가 있다면, 4개의 구획으로 나누어 다시 기계를 확인한다.
4. 모든 기계가 파괴될 때까지 2-3단계의 작업을 반복한다.

2. 입력

첫번째 줄에는 격자판 크기 N이 주어진다. 이때 N은 항상 2^k(2의 지수승) 형태이다. 

 

두번째 줄부터 N x N 행렬에 기계번호 3이하의 자연수가 주어진다.

3. 출력

기계의 최소 공격횟수

4. 알고리즘 : 분할정복

이 문제는 공격 가능한 경우와 공격하지 못하는 경우를 생각하면 된다. 공격 가능한 경우, 즉, 모든 기계의 번호가 같은 경우에는 공격한다. 그렇지않은 경우, 즉, 다른 기계가 섞여있는 경우에는 행렬을 4등분한다.

 

• N x N 행렬의 모든 기계 번호를 확인한다.
• 1) 만약 모든 기계의 번호가 같다면 공격횟수를 1증가시킨다.
• 2) 하나라도 다른 번호가 있다면 행렬을 4등분시키고 다시 번호를 확인한다.
• 모든 기계가 파괴되기 전까지 위의 과정을 반복한다.

5. 코드

# 입력처리
n = int(input())
enemy = [list(map(int, input().split())) for _ in range(n)]

cnt = 0 # 공격횟수 카운트 변수

def attack(row, col, size) : # 공격하는 격자판 시작좌표와 격자판 크기를 입력받는다.
    global cnt
    if size == 1: # 격자판 크기가 1인 경우에는 반드시 같은 기계만 있다.
        cnt += 1 # 따라서 공격가능
        return
    
    # 그렇지않은 경우 : 격자판 크기가 1 초과인 경우
    start = enemy[row][col] # 다른기계가 섞여있는지 확인하기 위한 기준 기계번호
    canAttack = True # 공격가능 여부 flag boolean 변수
	
    # 다른기계가 섞여있는지 체크
    for i in range(size):
        for j in range(size):
            if enemy[row + i][col + j] != start: # 하나라도 다른기계가 있다면 break
                canAttack = False
                break
        if not canAttack:
            break
	
    # 공격할 수 없는 경우 격자판 구역을 4등분한다.
    if not canAttack:
        next_size = size // 2
        attack(row, col, next_size)
        attack(row + next_size, col, next_size)
        attack(row, col + next_size, next_size)
        attack(row + next_size, col + next_size, next_size)
    else: # 모두 같은 기계인 경우 공격횟수 + 1
        cnt += 1

attack(0, 0, n)
print(cnt)