카카오프렌즈 컬러링북 - c++ (2017 카카오코드 예선)

 

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

프로그래머스

이문제는 dfs를 이용하여 문제를 풀었습니다. bfs를 통하여서도 문제를 풀수 있는데 저같은 경우는 dfs가 더 편해서... 문제를 풀기 위한 아이디어는 다음과 같았습니다.

1. 해당 지역을 방문 했는지 하지 않았는지를 구분하는 어레이가 필요합니다.
2. 각각의 지역을 방문하면서 0이 아니고 방문하지 않았더라면 dfs함수를 실행을 합니다.
=> 처음 해당 지역을 방문하게 되면 지역의 갯수에 대한 변수를 +1해줍니다.
=> 이때 다른 지역을 방문할 차례가 되게 되면 자신의 순서(count)를 리턴 합니다.
4. 해당 지역에 대한 넓이를 dfs가 최종적으로 리턴을 하고 이것을 전의 값과 비교하여 최대 지역의 넓이로 사용을 합니다.

#import <iostream>
#import <vector>
#include <cstring>

int visit[100][100]={false};//방문 여부를 확인하는것(재방문 하지 않도록)
vector<vector<int>> pic;
vector<pair<int,int>> direction;
int width,height;

int dfs(int y, int x, int cnt){
	//해당 지역을 방문했으니 true로 바꾸어주기
	visit[y][x] = true;
    
    for(int i=0;i<4;i++){
    	int nextY = y+direction[i].first;
        int nextX = x+direction[i].second;
        
        //그림의 범위에서 벗어나지 않도록 하기 위한것
        if(nexY>=height||nextX>=width||nextY<0||nextX<0) continue;
        //다음지역과 현재지역이 같고, 방문하지 않았다면 더 깊게 탐색!(다음 지역과 현재의 지역의 값이 같아야 같은 지역으로 판단)
        if(pic[nextY][nextX]==pic[y][x]&&visit[nextY][nextX]==false){
        	cnt = dfs(nextY,nextX,cnt+1);
        }
    }
    return cnt;
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
	vector<int> answer;
    int number_of_area = 0;//지역의 갯수
    int max_size_of_one_area = 0;//지역중 가장 넓은 지역의 크기
    
	pic = picture;
    width = m;
    height = n;
    
    //다음 상,하,좌,우 위치의 값을 확인하기 위한 값들 
    direction.push_back(make_pair(0,1));
    direction.push_back(make_pair(0,-1));
    direction.push_back(make_pair(1,0));
    direction.push_back(make_pair(-1,0));
    
    for(int i=0;i<m;i<++){
    	for(int j=0;j<n;j++){
        	//0일때는 문제에서 구역으로 삼지 않겠다고 했음. 또한, 해당 지역을 방문하지 않았어야 한다.
        	if(picture[i][j]!=0&&visit[i][j]==flase){
            	number_of_area++;
                max_size_of_one_area = max(max_size_of_one_area,dfs(i,j,1))
            }
        }
    }
    
    answer.push_back(number_of_area);
    answer.push_back(max_size_of_one_area);
    return answer;
}