풀이: x1, y1, x2, y2로 가로 세로로 이분탐색을 해주면서 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래
순서대로 return을 해줍니다.
base condition: y1 < x1, y2 < x2, for문으로 확인 후 더 탐색할지 말지를 결정
for문을 체크 후 조건이 맞지 않는다면 더 분할하여 탐색하는 방법입니다
#include <iostream>
using namespace std;
int n;
char num[65][65] = {0,};
int arr[65][65] = {0,};
string qurdTree(int x1, int y1, int x2, int y2) {
if(y1 < x1) return "";
if(y2 < x2) return "";
int oneCheck = 0;
int zeroCheck = 0;
for(int i = x1; i <= y1; i++) {
for(int j = x2; j <= y2; j++) {
if(1 == arr[i][j]) {
oneCheck++;
}
else {
zeroCheck++;
}
}
}
if(oneCheck == 0) {
return "0";
}
else if(zeroCheck == 0) {
return "1";
}
int mid1 = (x1 + y1) / 2;
int mid2 = (x2 + y2) / 2;
return "(" + qurdTree(x1, mid1, x2, mid2) + qurdTree(x1, mid1, mid2+1, y2) + qurdTree(mid1+1, y1, x2, mid2) + qurdTree(mid1+1, y1, mid2+1, y2) + ")";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
cin >> num[i][j];
}
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
arr[i][j] = num[i][j] - 48;
}
}
cout << qurdTree(1,n, 1, n);
}
'개발 > 알고리즘' 카테고리의 다른 글
경북SW 한‧베 국제SW코딩경진대회 참가후기 (0) | 2024.09.02 |
---|---|
백준 15683번 감시 (골드 3) 백트래킹, 시뮬레이션 (0) | 2024.07.19 |
엘리스 코드 챌린지 1번 풀이 (0) | 2024.07.08 |
백준 10971 (백트래킹 실버-2) (0) | 2024.07.06 |
14500 테트로미노 (2) | 2024.06.09 |