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

1. 문제

---

 

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

 

 

2. 소스코드

---

- 대놓고 BFS 쓰라는 문제라서 무난했다.

- 전역변수로 선언해도 초기화를 해주지 않으면 에러가 났다. 전역변수 기본 초기화가 안 먹는 문제인듯.

1) 배열 전체를 돌면서, 0이 아니고, 방문 하지 않은 위치를 BFS한다. 발견 시, 새로운 구역이므로 구역 수++

2) 해당 영역을 모두 탐색하고 area 넓이를 반환한다.

3) 정답과 비교 후 최대 크기인 경우, 갱신한다.

4) 1으로 돌아가 반복한다.

 

소스코드

#include <vector>
#include <iostream>
#include <queue>
#define MAX 100

using namespace std;
int visited[MAX][MAX];
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };

int bfs(int i, int j, int land, int m, int n, vector<vector<int>> picture) {
    int area = 1;
    queue<pair<int, int>> que;
    que.push({ i,j });
    visited[i][j] = true;
    while (!que.empty()) {
        int x = que.front().first;
        int y = que.front().second;
        que.pop();
        for (int k = 0; k < 4; ++k) {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (nx >= m or ny >= n or nx < 0 or ny < 0) continue;
            if (visited[nx][ny] or picture[nx][ny] != land) continue;
            que.push({ nx,ny });
            visited[nx][ny] = true;
            area++;
        }
    }
    return area;
}

 
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0;
    int max_size_of_one_area = 0;

    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            visited[i][j] = 0;
 
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            if (!visited[i][j] and picture[i][j]) {
                int temp = bfs(i, j, picture[i][j], m, n, picture);
                number_of_area++;
                if (temp > max_size_of_one_area) 
                    max_size_of_one_area = temp;
            }
        }

    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}