2605 codeup문제 캔디팡 floodfill문제

codeup.kr/problem.php?id=2605

캔디팡

#include <iostream>
using namespace std;

int board[9][9];
int	cnt[9][9];
int d = 0;
int ret;

void	init_cnt()
{
	int i;
	int j;

	for (i = 0; i <= 8; i++)
	{
		for (j = 0; j <= 8; j++)
		{
			cnt[i][j] = 0;
		}
	}

}

void	input_board()
{
	int i;
	int j;

	for (i = 1; i <= 7; i++)
	{
		for (j = 1; j <= 7; j++)
		{
			cin >> board[i][j];
		}
	}

}

int dfs(int i, int j)
{
	int newx;
	int newy;
	int arr[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}};

	if (i < 1 || i > 7 || j < 1 || j > 7)
	{
		return 0;
	}
	d++;
	cnt[i][j] = 1;
	for (int k = 0; k < 4; k++)
	{
		newx = i + arr[k][0]; //new
		newy = j + arr[k][1];
		if (board[newx][newy] == board[i][j] && cnt[newx][newy] == 0)
		{
			dfs(newx, newy);
		}
	}
	return (ret);
}

void	print_cnt()
{
	int i, j;

	for (i = 0; i < 9; i++)
	{
		for (j = 0; j < 9; j++)
		{
			cout << cnt[i][j];
		}
		cout << endl;
	}
	cout << endl;
}

int main(void)
{
	int i;
	int j;

	init_cnt();
	input_board();
	ret = 0;
	for (i = 1; i <= 7; i++)
	{
		for (j = 1; j <= 7; j++)
		{
			d = 0;
			if (cnt[i][j] == 0)
			{
				dfs(i, j);
			}
			if (d >= 3)
			{
				//print_cnt();
				//cout <<i << j<< ret<<endl;
				ret++;
			}

		}
	}
	//print_cnt();
	cout << ret;
}
/*
4 4 4 4 1 4 3
4 4 4 4 3 2 4
4 4 4 4 5 5 4
4 4 4 4 2 1 3
5 5 3 2 4 4 4
2 1 1 3 4 4 4
5 4 5 5 4 4 4
answer : 2
4 1 3 1 5 3 4
2 5 4 1 2 5 2
1 5 4 4 2 4 5
4 5 1 2 4 5 2
5 5 5 3 5 1 5
5 1 1 2 4 4 2
4 2 4 2 3 3 5
answer : 2
*/

dfs로 플러드필 푸는 문제다 

if (d >= 3)

부분을 어디에 놓느냐에 따라 계속 틀려서 힘들었다. 

 

dfs로 같은 것을 찾는 데까지 계속 들어가고, 

탐색한 위치는 같은 것이자, 한번 본 것이므로 cnt[][]배열로 visited를 체크한다. 

 

dfs가 다 끝나고 나온 후에는 3개이상 같은지를 d>=3으로 판단. 

재귀함수이므로 나오는 탈출 조건 역시 명시해야한다. 1~7 범위 

 

9*9로 만든 것은 어디서 그렇게 만드는게 세이프하다해서.. 

newx newy 값이 dfs에 들어가고 나서 판단하는 식이라서 그런 것 같다.