[프로그래머스] 카카오프렌즈 컬러링북 / DFS과 BFS, memset

문제

 

풀이

#include <vector>
#include <string.h> // memset
using namespace std;

bool visit[100][100];
int num , cnt, N, M;
int dx[4];
int dy[4];

//깊이탐색
//DFS : 깊이우선탐색
void DFS(int x, int y, vector<vector<int>> picture, int num) {
	visit[x][y] = true;
	cnt++;
	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
		if (picture[nx][ny] == num && !visit[nx][ny]) {
			DFS(nx, ny, picture,picture[nx][ny] );
		}
	}
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0; // 구역
    int max_size_of_one_area = 0; // 가장 큰 구역 칸 개수
    memset(visit,false,sizeof(visit)); // 배열 초기화
    num =0, cnt = 0;
    N = n;
    M = m;
    dx[0] = 0, dx[1] = 0,dx[2] = 1,dx[3] = -1;
    dy[0] = 1, dy[1] =-1, dy[2] = 0,dy[3] = 0;

    
    for(int i=0; i<m; i++){
        for(int j=0; j<n; j++){
            if(!visit[i][j] && picture[i][j] != 0) {
                cnt = 0;
                DFS(i,j,picture,picture[i][j]);
                number_of_area++;
                if(cnt > max_size_of_one_area) max_size_of_one_area = cnt;
                cnt = 0;
            }
        }
    }
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}

DFS(깊이 우선 탐색 )을 이용하여 구현했다.

 

 

 

memset

- 함수 원형 : void* memset(void* ptr, int value, size_t num);

- 첫 번째 인자 : 세팅하고자 하는 메모리의 시작 주소. 즉, 그 주소를 가리키고 있는 포인터가 위치하는 자리

- 두번째 인자 : 세팅하고자 하는 값

- 세번째 인자 : size_t num은 길이를 뜻한다. 보통 "길이 * sizeof(데이터 타입)"의 형태로 작성한다.

- 반환 값은 성공하면 첫 번째 인자로 들어간 ptr을 반환하고, 실패한다면 NULL을 반환한다.

- 헤더 파일 : memory.h 혹은 string.h
->배열에 사용

 

 

 

 

 

DFS( Depth-First Search / 깊이 우선 탐색)

- 해당 노드의 자식 노드들을 모두 탐색한 후 형제 노드를 탐색한다.

- 스택 또는 재귀 함수를 사용하여 구현한다.

 

BFS( Breadth-First Search / 너비 우선 탐색)

 - 시작 정점에 인접한 모든 정점들을 우선 방문하는 한 후, 탐색한 정점들에서 인접한 모든 정점들을 방문한다.

- 큐를 사용하여 구현한다.

 

 

DFS와 BFS는 중요하다고 생각하기 때문에 따로 글을 작성해 놓았다. 밑 링크를 참고!

https://strong-2-min.tistory.com/79

그래프 - DFS 와 BFS

 

 

---

다른 사람 풀이

#include <vector>
#include <queue>
#include <utility>
using namespace std;

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
const int INF = 1e9;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            picture[i][j] = -picture[i][j];
    int cnt = 0;
    int dx[] = { 0,0,1,-1 };
    int dy[] = { 1,-1,0,0 };

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            if (picture[i][j] < 0)
            {
                cnt++;
                int num = picture[i][j];
                queue<pair<int, int > > q;
                q.push(make_pair(i, j));
                while (!q.empty())
                {
                    int cx = q.front().first;
                    int cy = q.front().second;
                    q.pop();
                    for (int k = 0; k < 4; ++k)
                    {
                        int nx = cx + dx[k];
                        int ny = cy + dy[k];
                        if (nx >= 0 && nx < m && ny >= 0 && ny < n && picture[nx][ny] == num) {
                            picture[nx][ny] = cnt;
                            q.push(make_pair(nx, ny));
                        }
                    }
                }
            }
    int cnt_chk[10001] = { 0 };
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cnt_chk[picture[i][j]]++;
    int ans = 0;
    for (int i = 1; i < 10001; ++i)
        ans = max(cnt_chk[i], ans);
    return vector<int> {cnt, ans};
}

BFS(너비 우선 탐색)를 사용한 풀이이다.

 

 

 

---

https://blog.hexabrain.net/268

알고리즘 4-1강. 깊이 우선 탐색(Depth First Search)

https://blog.hexabrain.net/269?category=431859 

알고리즘 4-2강. 너비 우선 탐색(Breadth First Search)

https://soobarkbar.tistory.com/61

DFS (Depth-First Search) & BFS (Breadth-First Search)

https://blockdmask.tistory.com/441

[C언어/C++] memset 함수 메모리 초기화

https://hini7.tistory.com/66#toc-2.%20memset%20%ED%95%A8%EC%88%98%20%EC%9D%B4%EC%9A%A9

[c++] 배열 및 (STL) vector 초기화 방법 정리