백준 1992번 쿼드트리 (C++)

문제

정답 코드

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int check_all_same(int x,int y,int size,vector<vector<int>> &bmap)
{
	int start = bmap[y][x];
	for (int i=y; i < y + size;i++)
	{
		for (int j=x; j <x+ size;j++)
		{
			if (bmap[i][j] != start)
				return (0);
		}
	}
	return (1);
}

void	recur(int x,int y,int size,vector<vector<int>> &bmap)
{
	if (size == 1|| check_all_same(x,y,size, bmap))
	{
		cout << bmap[y][x];
	}
	else
	{
		cout << "(";
		recur(x,y,size/2,bmap);
		recur(x + size/2,y,size/2,bmap);
		recur(x,y+ size/2,size/2,bmap);
		recur(x+ size/2,y+ size/2,size/2,bmap);
		cout << ")";
	}
}

int main()
{
	int n;
	cin >> n;

	vector <vector<int>> bmap(n+1,vector<int>(n+1, 0));
	string s;
	for (int i=1;i <= n;i++)
	{
		cin >>s;
		for (int j=1;j <= n;j++)
		{
			bmap[i][j] = (int)(s[j - 1]-'0');
		}
	}
	// if (check_all_same(1,1,n,bmap) ==1)
	// {
	// 	cout << "(";
	// 	cout << bmap[1][1];
	// 	cout << ")";
	// }
	// else
		recur(1,1,n,bmap);
}

옛날 버전도 있어요

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<utility>

using namespace std;

int arr[65][65];

bool chk_all_same(int x,int y, int size)
{
	int t =arr[y][x];
	for (int i=0;i < size;i++)
	{
		for (int j=0; j<size;j++)
		{
			if (t != arr[i+y][j+x])
				return(0);
		}
	}
	return (1);
}

// void	print_arr(int x, int y, int size)
// {
// 	for (int i=0; i <size;i++)
// 	{
// 		for (int j=0; j<size;j++)
// 		{
// 			cout << arr[y+i][x+j];
// 		}
// 	}
// }


void	recur(int x,int y, int size)
{
	if (size == 1)
	{
		cout << arr[y][x];
		return ;
	}
	if (chk_all_same(x,y,size))
	{
		cout << arr[y][x];
		return ;
	}
	else
	{
		cout << "(";
		for (int i=0; i<2;i++)
		{
			for (int j=0; j<2;j++)
			{
				recur(x+j*(size/2),y+i*(size/2),size/2);
			}
		}
		cout <<")";
	}
}

int main()
{

	ios :: sync_with_stdio(0);
	cin.tie(0);
	int input;
	cin >> input;
	string s;

	for (int i=1; i <=input; i++)
	{
		cin >> s;
		for (int j=1; j<=input;j++)
		{
			arr[i][j] = s[j-1] - '0';
		}
	}
	// cout << "(";
	recur(1,1,input);
	// cout << ")";
}

문제 풀이의 흐름

• 계속 범위를 잘라가면서 안으로 들어가니까 4개로 자르는 재귀 문제겠다 싶었다.

• 함수로 잘라서

• 재귀 종료 조건을 모두가 같은 경우와 사이즈가 1인 경우로 제약을 줬다.

• 처음에는 1이 들어오고 1 인경우는 (1)이렇게 되야 한다고 생각했는데 사실 그게 아니었다.

• 그걸 고치니까 바로 해결 되었다.

주의 할 점

• 처음에는 1이 들어오고 1 인경우는 (1)이렇게 되야 한다고 생각했는데 사실 그게 아니었다.

• 1이 들어온다면 꼭 1만 출력해줘야 한다.

• 즉 하나도 안 감싸진 출력물이 있을 수 있다는 것이다 .

반성 및 고찰

손코딩이 확실히 코드부터 짜기 시작했을 때 보다 훨씬 더 효율적으로 빨리 짤 수 있는 것 같다.

머리로 한번에 하고 싶지만 그런 머리가 안되서 나중에는 손코딩이 아니더라도 천천히 생각하면서 코드를 짤 수 있으면 좋겠다.

손코딩

Uploaded by N2T