백준 2630번 색종이 만들기 [DFS]

문제

 

 

 

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------

 

문제 접근 순서.

 

1. 처음에 문제를 접했을 때 문제를 해결 방식을 소분화 하여 생각했다.

    어떻게 검사를 시작할지 ( ex 모든 색종이가 파란색 or 하얀색 /  색종이를 어떻게 분할 할지 등) 

 

2. 계속 생각하던 중 색종이가 계속 자기 분열 즉 재귀적으로 계속 분할하는 것을 볼 수 있어서 

    DFS 알고리즘이 생각났다. 

 

3.  따라서 DFS 알고리즘을 사용하며 해당 색종이가 분할하면 4개의 색종이가 생기므로 

     DFS 안에서 다시 4개의 DFS를 호출하는 방안을 생각했다. 

 

 

---------------------------------------------------------------------------------------------------------------------------------------------------------------

 

코드

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

vector<vector<int>> paper;
int whiteCnt = 0;
int blueCnt = 0;

void dfs(int r, int c, int size)
{
    int color = paper[r][c];
    bool same = true;

    // 현재 영역이 모두 같은 색인지 검사
    for (int i = r; i < r + size; i++)
    {
        for (int j = c; j < c + size; j++)
        {
            if (paper[i][j] != color)
            {
                same = false;
                break;
            }
        }
        if (!same) break;
    }

    // 모두 같은 색이면 카운트 후 종료
    if (same)
    {
        if (color == 0) whiteCnt++;
        else blueCnt++;
        return;
    }

    // 아니면 4등분
    int half = size / 2;

    dfs(r, c, half);                 // 왼쪽 위
    dfs(r, c + half, half);          // 오른쪽 위
    dfs(r + half, c, half);          // 왼쪽 아래
    dfs(r + half, c + half, half);   // 오른쪽 아래
}

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

    paper.assign(n, vector<int>(n));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> paper[i][j];

    dfs(0, 0, n);

    cout << whiteCnt << "\n";
    cout << blueCnt << "\n";

    return 0;
}

 

 

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

 

다시 풀어본  코드

 

#include <iostream>
#include <vector>

using namespace std; 

int g_WhiteCount = 0; 
int g_BlueCount = 0;

void DFS(vector<vector<int>>& _vec, int _iStart_Row, int _iStart_Col, int _iSize)
{
	int  thisPaperColor = _vec[_iStart_Row][_iStart_Col];
	bool bAllPaperColorSame = true; 

	for (int i = _iStart_Row; i < _iStart_Row +_iSize; i++)
	{
		for (int j = _iStart_Col; j<_iStart_Col+_iSize; j++)
		{
			if (thisPaperColor != _vec[i][j])
			{
				bAllPaperColorSame = false;
				break;
			}
			if (!bAllPaperColorSame)
				break;
		}
	}

	if(bAllPaperColorSame)
	{
		switch (thisPaperColor)
		{
		case 0:
			g_WhiteCount++;
			break;
		case 1:
			g_BlueCount++;	
			break;
		}

		return;
	}

	int iNextSize = _iSize / 2;

	DFS(_vec, _iStart_Row, _iStart_Col, iNextSize); // 왼 위 
	DFS(_vec, _iStart_Row + iNextSize, _iStart_Col, iNextSize); // 오른 위
	DFS(_vec, _iStart_Row , _iStart_Col + iNextSize, iNextSize); // 왼 아래 
	DFS(_vec, _iStart_Row + iNextSize, _iStart_Col + iNextSize, _iSize / 2); // 오른 아래 


	
}

int main()
{
	int i_WhiteCount = 0; 
	int i_BlueCount = 0;
	int i_inputLineSize = 0; 
	cin >> i_inputLineSize; 

	vector<vector<int>> m_vecPaper(i_inputLineSize, vector<int>(i_inputLineSize,0));

	int row = i_inputLineSize;
	int col = i_inputLineSize; 

	
	for (int i = 0; i < row; i++) 
	{
		for(int j=0; j <col; j++)
		{
			cin >> m_vecPaper[i][j]; 
		}
	}

	
	DFS(m_vecPaper, 0,0,i_inputLineSize);


	cout << g_WhiteCount << "\n";
	cout << g_BlueCount;







	return 0;
}