C++) 백준 1780 종이의 개수

문제

 

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

1780번: 종이의 개수

 

왼쪽과 같이 INPUT으로 N * N 종이가 들어온다. (N은 3의 거듭제곱)

종이가 모두 같은 숫자로 이뤄져 있으면 그대로 사용하고 (모두 -1 or 모두 0 or 모두 1)

그렇지 않다면 9등분 하여 각각의 종이를 확인한다.

 

내 알고리즘

 

1. 2차원 배열에 INPUT 값을 저장한다.

2. Find 함수에 2차원 배열을 넘기고 전체 종이가 같은 값으로 이뤄져있는지 확인한다.

3 - 1. 모두 같은 값이라면  result 배열 경신 후 return,

3 - 2. 아니라면 종이를 9등분 하여 각각 재귀 함수를 호출한다.

 

 

내 풀이

 

 

#include <iostream>
#include <vector>

using namespace std;

int num[3] = {0, }; // result 배열. 각각 -1 종이 개수, 0 종이 개수, 1 종이 개수 

void Find(vector< vector<int> > &v, int ystart, int yend, int xstart, int xend)
{
	int firstNum = v[ystart][xstart]; // 기준값 설정 (종이의 맨 위 맨 왼쪽)
	bool failCheck = false; // 주어진 종이가 모두 같은 값으로 이뤄졌는지 체크
	int i;
	int j;

	if (yend - ystart == 1) // 변의 길이가 1이라면 아래를 진행하지 않고
	{
		num[firstNum + 1]++; // result 배열 경신 후 return
		return; 		// firstNum은 -1, 0, 1 이기에 +1 하여 num[3]에 담기
	}

	for(i = ystart; i < yend; i++)
	{
		for(j = xstart; j < xend; j++)
		{
			if (v[i][j] != firstNum) // 모두 같은 값인지 체크 (설정값과 모두 같은지)
			{
				failCheck = 1; // 아니라면 for문 탈출
				break;
			}
		}
		if (failCheck) // 아니라면 for문 탈출
			break;
	}

	if(!failCheck) // 모두 같은 값이라면
	{
		num[firstNum + 1]++; // result 배열 경신 후 return
		return;
	}

	int gap = (yend - ystart) / 3; // 변의 길이를 3등분 하기

	for (i = ystart; i < yend; i += gap) // y변 3등분
		for (j = xstart; j < xend; j += gap) // x변 3등분
			Find(v, i, i + gap, j, j + gap); // 3등분한 y, x 시작값에 변의 길이를 더한 끝값을 넘김
            						// 그러므로 9개의 영역을 넘길 수 있음
}

int main()
{
	int N;

	cin >> N;
	vector< vector<int> > v(N, vector<int>(N, 0)); // N * N 의 2차원 배열 초기화
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
				cin >> v[i][j];
	Find(v, 0, N, 0, N); // (배열, y시작값, y끝값, x시작값, x끝값) 을 넘김
	cout << num[0] << endl;
	cout << num[1] << endl;
	cout << num[2] << endl;
}

 

 

알게된 점

 

 

1. 배열을 넘길 때, 쓸데없이 call by value 를 사용하지는 않는지 주의하기

 

처음에 시간 초과가 나왔다.

2차원 배열을 넘길 때, 참조형 변수를 사용하지 않고 ( &v) 그냥 배열을 받아오게끔 함수를 만들었기 때문이다. (v)

재귀 함수를 호출할 때 마다 쓸데없이 2차원 배열이 복사되었고 시간, 공간이 매우 크게 낭비되었다.

 

 

2. N의 길이가 범위가 크게 가변적일 때, 어떻게 전역변수로 사용 가능할 지

 

C에서는 2차원 포인터를 전역 변수로 선언한 후에, main 함수에서 N의 길이를 알게된 후 2차원 for문으로 malloc을 해줬었다.

C++을 사용하고 나서 배열의 크기를 유동적으로 변동할 수 있는 벡터를 이용하게 되었지만, 2차원 벡터에 대해서는 항상 어려움을 겪었다.

C++에서 2차원 배열을 선언하는 방법은 다음과 같다.

 

vector< vector<int> > v (N, vector<int>(N, 0));

 

위 코드가 N * N이 0으로 할당된 2차원 벡터 만들기.

 

위의 방식은 선언과 동시에 초기화해줘야 하기 때문에 전역변수 선언 후 N * N 을 나중에 할당하려면 다른 방법을 써야한다.

 

 

1.  이미 선언된 2차원 배열에 N * N 만큼 0으로 초기화하는 방법

#include <iostream>
#include <vector>

using namespace std;

int num[3] = {0, };
vector< vector<int> > v; // 2차원 벡터를 선언

void Find(int ystart, int yend, int xstart, int xend)
{
	// 매개변수에 2차원 배열이 지워졌다.
}

int main()
{
	int N;

	cin >> N;

	vector<int> hi;
	for (int i = 0; i < N; i++) // N개의 0이 들어간 1차원 벡터 생성 후
		hi.push_back(0);
	for (int i = 0; i < N; i++) // N개의 1차원 벡터를 2차원 벡터에 넣음
		v.push_back(hi);

	// 생략
    
	Find(0, N, 0, N);

	// 생략
    
}

 

 

2. 혹은 new 를 이용하여 이미 선언된 2차원 배열에 N * N 만큼 0으로 초기화할 수 있다.

 

#include <iostream>
#include <vector>

cin >> N;

int** ary = new int*[N]; 
for(int i = 0; i < N; ++i)
    ary[i] = new int[N];

 

2번의 방식이 C에서의 2중 for문을 활용한 malloc과 비슷하다.

하지만 Java도 아닌 C++에서의 new는 아직 나에게 낯선 것 같다.