[アルゴリズム]CODEUP#2605:Candy Fang


CodeUp#2605:Candy Fang
使用言語:c++
質問分類:DFS、BFS
<解答>
これはDFSを利用して解決した問題で、同じインデックスをチェックする条件を入れれば、難しく解決しない問題です!
#include <iostream>
using namespace std;

int dfs(int x, int y);

int check[8][8] = { 0 }; 
int color[8][8] = { 0 }; 
int dx[4] = { -1 , 0 , 1 , 0 };
int dy[4] = { 0 , -1 , 0 , 1 };
int count = 0;

int main(void)
{
	int num = 0;
	for (int i = 1; i <= 7; i++)
	{
		for (int j = 1; j <= 7; j++)
		{
			cin >> color[i][j]; //캔디 색 
		}
	}
	for (int i = 1; i <= 7; i++)
	{
		for (int j = 1; j <= 7; j++)
		{
			if (dfs(i, j) >= 3) { num++; }
		}
	}
	cout << num << endl;
}

int dfs(int x, int y)
{
	int nx, ny;
	int count = 1; // 처음 선택한 것도 count
	check[x][y] = 1; // 시작 부분 방문 체크  

	for (int i = 0; i < 4; i++) { // 상, 하, 좌, 우 인접한 부분 탐색 
		nx = x + dx[i]; 
		ny = y + dy[i];

		if (nx <= 7 && nx >= 1 && ny <= 7 && ny >= 1) // 7*7 조건이므로 제한 
		{
			if (check[nx][ny] == 0 && color[x][y] == color[nx][ny]) // 같은 색인지 체크
			{
				count += dfs(nx, ny); // 1씩 증가함 
			}
		}
	}
	return count;
}