문제
아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.
전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.
전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.
위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.
입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.
출력
첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.
주어진 조건에 맞을때 기존 역역을 4분할 하는 문제이며 이런 방식을 쿼드 트리 라고 한다.
경우의 수가 두개인 상황이라 분할정복 - 쿼드트리 문제의 입문이라고 볼 수 있겠다.
분할정복 알고리즘 ?
기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트나 병합정렬이 있다.
출처 : 나무위키 - 분할 정복 알고리즘
사실 처음엔 큰 문제를 작게 쪼개서 계산?? 이 문제에 적용이 된다고? 싶었지만 처음 접해보는 분할정복 문제였어서 감이 안왔던듯 하다.
직접 문제를 손으로 써내려가면서 이해해 보았다.
문제에서 주어진 조건은 크게 두가지가 있다.
1. 주어진 영역 내 서로 다른 색이 존재 할 경우 해당 영역을 4분할 한다.
2. 정사각형 내 동일 색상 단위로 총 몇개 정사각형이 존재하는지 출력한다.
따라서 1번 조건에 맞을 경우 문제를 쪼개면 되는것이고, 쪼갠 상황에서 2번 조건에 맞는다면 답으로 기록하면 된다.
시작점은 [0, 0] 으로 한다. 시작점의 색상을 기억해 두고, 일정한 인접 행렬을 탐색하다가 다른 값이 나온다면 1번 조건에 부합하므로 즉시 4분할을 해준다.
분할된 영역의 구간은 규칙적으로 변경된다.
python의 // 는 값을 나눈 몫을 반환하므로 n값이 8일때 n//2를 하면 그 값은 4가 된다. 또한 python의 for loop에서 range의 end parameter는 해당 값 "미만"으로 동작하기 때문에 n//2 값을 넣어주면 된다.
처음에 탐색의 시작을 [0,0] 에서 한다고 하였으므로 첫번째 이중 for loop의 탐색 범위는 탐색x는 (이하 xx) x ~ x+n(미만) 이고, 탐색y는 (이하 yy) y ~ y+n 이 된다.
첫번째 cut 에서 또다시 서로다른 색이 발견되어 4분할을 진행해 줄때, x값과 y값의 범위 변화는 규칙적으로 변경된다.
위 규칙을 토대로 풀이를 작성하면 아래와 같다.
import sys
sys.stdin = open("input.txt")
n = int(input())
board = [list(map(int, input().split())) for _ in range(n)]
white = 0
blue = 0
def cut(x, y, n):
global white
global blue
check_color = board[x][y]
for xx in range(x, x+n):
for yy in range(y, y+n):
if board[xx][yy] != check_color: # 조건 1 부합 : 4분할 진행
cut(x=x, y=y, n=n//2) # 1영역 : x = x ~ x+(n//2) | y = y ~ y+(n//2) | n = n//2
cut(x=x, y=y+n//2, n=n//2) # 2영역 : x = x ~ x+(n//2) | y = y+n//2 ~ y+n//2+n | n = n//2
cut(x=x+n//2, y=y, n=n//2) # 3영역 : x = x+n//2 ~ x+n//2+n | y = y ~ y+(n//2) | n = n//2
cut(x=x+n//2, y=y+n//2, n=n//2) # 4영역 : x = x+n//2 ~ x+n//2+n | y = y+n//2 ~ y+n//2+n | n = n//2
return # 분할은 분할대로 호출해놓고, 값에 적용되는걸 막기 위해 분할 뒤 return 한다.
# 조건 2 부합 : 분할되지 않으면 모두 색이 같다는 것으로 정답으로 기록한다.
if check_color == 1:
blue += 1
else:
white += 1
cut(0, 0, n) # 시작 조건 [0,0]
print(f"{white}\n{blue}")
큰 문제를 쪼갠다는 것과, 4분할 처리 하는 것에 대해 알 수 있었다.!
'풀이로그' 카테고리의 다른 글
| [백준] 20168, 20182, 20183 python : dfs 활용, 이분탐색과 다익스트라 활용 (0) | 2024.03.14 |
|---|---|
| [백준] 11403 python 플로이드 워셜, deque 풀이와 시간복잡도 비교하기 (0) | 2024.03.10 |
| [백준] 2792 Python | 15810 Python : 이분탐색법 (0) | 2024.03.03 |
| [알고리즘] 백준 | 배열 돌리기 Python (16926, 16927) (2) | 2024.02.14 |
| [Java] 코딩테스트 값 입력받는 방법 : Scanner, next(), nextInt(), nextLine() (0) | 2024.02.02 |
