[프로그래머스] 카카오프렌즈 컬러링 북 C++ (dfs)

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

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

 

재귀함수를 사용한 DFS 알고리즘으로 구현

각 셀의 위 아래 오른쪽 왼쪽 4방향을 탐색하며 해당 셀이 현재 셀과 같은 색의 영역일 경우 다시 dfs에 돌입

하나의 영역을 탐색한 후 해당 영역의 셀의 개수를 반환하며 dfs 탈출

 

셀을 한칸한칸 탐색하며 탐색하지 않은 셀일 경우 다시 dfs를 불러 해당 영역을 모두 탐색

 

한 영역의 셀의 개수(cnt)들 중 가장 큰 값을 answer에 저장 (max함수)

 

 

풀이과정

1. main의 for문을 통해 모든 타일을 하나씩 탐색하며 dfs 함수 돌입

2. dfs 함수 내부에서 다시 for문을 통해 상, 하, 좌, 우 4개의 타일 탐색

 

3. 조건

 

인접 타일이 존재하면서 next_x >= 0 && next_y >= 0 && next_x < max_x && next_y < max_y

현재 타일과 인접 타일의 색상이 같고  pic[next_x][next_y]==pic[x][y]

그 인접 타일이 방문하지 않은 타일일 때 visit[next_x][next_y]!=1

 

카운트 (cnt) 증가 후 해당 타일의 좌표를 넣어 다시 dfs에 돌입

 

4. 하나의 섹션을 탐색하게 되면 섹션 크기의 최대값을 저장하는 변수 max_size_of_one_area 의 값과 비교하여

큰 값을 max_size_of_one_area 에 저장하고

총 섹션의 개수를 구하는 변수 number_of_area의 개수를 1 증가 후 dfs탈출

다시 main의 for문을 통해 다음 타일 탐색

----모든 타일 반복----

 

5. max_size_of_one_area, number_of_area 의 값을 결과로 리턴

 

 

vector<vector<int>> pic;
vector<vector<int>> visit;
vector<int> dx;
vector<int> dy;
int max_x;
int max_y;
int cnt;

int dfs(int x, int y) {
	visit[x][y] = 1;
	for (int i= 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x >= 0 && next_y >= 0 && next_x < max_x && next_y < max_y && pic[next_x][next_y]==pic[x][y] && visit[next_x][next_y]!=1) {		
			cnt++;
			dfs(next_x, next_y);
		}
	}
	return cnt;
}


vector<int> solution(int m, int n, vector<vector<int>> picture) {
	int number_of_area = 0;
	int max_size_of_one_area = 0;
	vector<int> answer(2);
	answer[0] = number_of_area;
	answer[1] = max_size_of_one_area;


	pic = picture;
	dx = { 0, 1, 0, -1};
	dy = { 1, 0, -1, 0 };
	max_x = m;
	max_y = n;
	vector<vector<int>> v(m, vector<int>(n, 0));
	visit = v;
	for (int i = 0; i < pic.size();i++) {

		for (int j = 0; j < pic[0].size(); j++) {

			if (visit[i][j] == 0 && pic[i][j]!=0) {
				cnt = 1;
				max_size_of_one_area = max(dfs(i, j), max_size_of_one_area);
				number_of_area++;
			}
		}
	}
	answer[0] = number_of_area;
	answer[1] = max_size_of_one_area;
	return answer;
}