백준 1992, 분할 정복 문제

https://www.acmicpc.net/problem/1992

1992번: 쿼드트리

해당 문제는 분할 정복 문제이다. 배열의 크기가 N X N일때, N은 2의 제곱수이기 때문에 2배 간격으로 범위를 지정할 수 있다. N의 최소 값은 1이므로 2차원 배열의 한 칸까지 분할될 수 있다. 필자는 int형을 반환하는 메서드를 작성하였는데, 해당 문제는 숫자 뿐만 아니라 괄호까지 출력해야 하기 때문에 string을 사용하는 것이 적합하다.

 

Key Point

1. 괄호가 묶이는 경우는 4개의 영역이 다 같은 값을 갖지 않을 경우이다. 따라서 4개의 영역을 탐색하는 로직이 필요하다. (이중 for문)
2. 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 이동하기 때문에 재귀함수를 작성할 경우, 시작 좌표를 전달하는 매개변수 설정을 잘 해야 한다.

문제 코드

#include <bits/stdc++.h>
using namespace std;

int N;
char arr[64][64];
string s;

string go(int size, int y, int x){
	if(size == 1) return string(1,arr[y][x]);
	
	char b = arr[y][x];
	
	for(int i = y; i < y + size; i++){
		for(int j = x; j < x + size; j++){
			if(b != arr[i][j]){
				string ret = "";
				ret += "(";
				ret += go(size/2, y, x);
				ret += go(size/2, y, x + size/2);
				ret += go(size/2, y + size/2, x);
				ret += go(size/2, y + size/2, x + size/2);
				ret += ")";
				
				return ret;
			}
		}
	}
	return string(1, arr[y][x]);
}

int main(){
	
	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> s;
		for(int j = 0; j < N; j++){
			arr[i][j] = s[j];
		}
	}
	cout << go(N, 0, 0) << "\n";

	return 0;
}

• char형을 string형으로 바꾸기 위해서는 string 생성자를 사용한다. string(1, char);
• 모든 요소의 값이 같은지 판단하는 이중 for문이 사용되었고, 같지 않을 경우에만 재귀함수가 실행된다.
  • 만약, 모든 요소가 같다면 0 또는 1만 출력하면 되기 때문에 마찬가지로 string(1, char);을 사용하였다.
  • 만약, 모든 요소가 같지 않다면 if문 로직이 실행되어 새로 생성된 ret를 반환한다.
• 각각의 재귀함수마다 지역변수인 ret을 생성하고 자신의 상위 재귀함수에게 ret을 반환한다.
  • 호출되었던 재귀함수들이 종료됨과 동시에 생성한 문자열을 차례대로 반환함으로써 최종적으로 첫 호출지점에서 순서대로 연결된 문자열 ret을 얻을 수 있다.

 

https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의