공부 자료/알고리즘
(C/C++) 백준 2630번 - 색종이 만들기
뚜루뚜루세니
2021. 7. 19. 21:32
728x90
문제출처: https://www.acmicpc.net/problem/2630
2630번: 색종이 만들기
첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다.
www.acmicpc.net
1. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int paper[128][128];
int white = 0;
int blue = 0;
int N;
void count(int n, int x, int y) {
int color = paper[x][y];
for (int i = x; i < x + n; i++) {
for (int j = y; j < y + n; j++) {
//색이 다르면 4등분
if (paper[i][j] != color) {
count(n / 2, x, y); //nw
count(n / 2, x + n / 2, y); //sw
count(n / 2, x, y + n/2 ); //ne
count(n / 2, x + n / 2, y + n/2); //se
return;
}
}
}
if (color == 1)
blue++;
else
white++;
}
int main() {
scanf("%d", &N);//한 변의 길이
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &paper[i][j]);
}
}
count(N,0, 0);
printf("%d\n%d", white, blue);
}
|
cs |
2. 해결과정
color 변수에 현재 색종이의 색을 할당해주고, 이중 for문을 이용하여 color와 다른 색상이 현재 사분면에 존재하는지 확인한다. color와 다른 색상이 존재하면 현재 사분면을 4등분하여 각각 나눠진 사분면을 재귀로 호출 -> 호출값을 return
(nw= 왼쪽 위, sw= 왼쪽 아래, ne =오른쪽 위, se=오른쪽 아래)
현재 사분면이 모두 같은 색이면 color 색상에 따라 white, blue 변수에 카운트 해주면 된다.
3. 느낀점
재귀를 사용하면 확실히 코드가 간결해진다. 재귀를 몰아서 왁 푸니까 재귀로 풀수 있었는데 과연 따로 존재하는 문제였다면 내가 재귀를 생각할 수 있었을까? 고민해봐야할듯,,, 공부하자!!
728x90