[C++/알고리즘] 프로그래머스 (카카오프렌즈 컬러링북)

 

https://programmers.co.kr/learn/courses/30/lessons/1829#

코딩테스트 연습 - 카카오프렌즈 컬러링북

 

 

재귀를 이용한 DFS 방식으로 풀었다.

방문한 픽셀은 color값을 0으로 바꿔주고 방문 시에 해당 픽셀의 color값을 비교해 같은 부분인지 체크하는 방식으로 풀었다. 

 

 

 

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

vector<vector<int>> v;
int sizeN, sizeM;
int maxSize = 0;

bool dfs(int x, int y, int color)
{
	if (x <= -1 || x >= sizeN || y <= -1 || y >= sizeM)
	{
		return false;
	}

	if (v[y][x] != 0 && v[y][x] == color)
	{
		v[y][x] = 0;
		maxSize += 1;
		dfs(x - 1, y, color);
		dfs(x, y - 1, color);
		dfs(x + 1, y, color);
		dfs(x, y + 1, color);
		return true;
	}
	return false;
}


vector<int> solution(int m, int n, vector<vector<int>> picture) {
	vector<int> answer(2, 0);
	int number_of_area = 0;
	sizeN = n;
	sizeM = m;
	v = picture;

	for (int i = 0; i < m; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (dfs(j, i, picture[i][j]))
			{
				number_of_area += 1;
				answer[1] = maxSize > answer[1] ? maxSize : answer[1];
				maxSize = 0;
			}
		}
	}
	answer[0] = number_of_area;
	return answer;
}

 

 프로그래머스 홈페이지에서 그냥 풀다가 dfs 함수를 if문으로 체크하는 부분에 i와 j를 반대로 줘서 분명 맞는데 왜 값이 다르게 나오지? 하고 디버깅까지 찍어봤다ㅠ

[y][x] 방식으로 이용하는데 함수에 인자로 넘겨줄 때 x,y 순서로 넘겨주고 있어서 문제가 생겼던 것이다...