[cpp]카카오프렌즈 컬러링북 - 2017 카카오코드 예선

 

그동안 푼 문제들을 하나씩 정리해서 조회수를 올려야겠다. 카카오 문제 위주로 올리면 많이 보겠지?

 

이 문제는 대표적인 BFS/DFS 문제로 정말 흔하게 많이 나오는 문제이다. 처음에 접근하기 힘들 수는 있지만, 유형만 익혀두면 쉽게 풀 수 있는 문제이니 이러한 유형을 꼭 익혀주도록 하자. 문제를 보자마자 기본 템플릿을 지워버려서 몰랐는데 전역변수 사용시 함수 안에서 초기화를 해야한다고 한다. 

 

풀이

1. 최대 영역 구하기

 그림의 영역 구분은 '상하좌우로 연결되어 있는지' 를 기준으로 한다. 따라서 탐색의 시작 좌표를 기준으로 상하좌우로 같은 색깔이 몇개나 있는지 체크해주면 된다. 이때 탐색은 (0,0) 영역부터 (m,n)영역까지 순차적으로 이동하며 수행한다. 같은 공간을 두번 체크하지 않도록 2차원 bool타입 배열인 vis를 사용하여 방문한 영역을 체크하였다.

 

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

...

auto curr = q.front(); q.pop();
for (int k = 0; k < 4; ++k) {
    int nx = curr.first + dx[k];
    int ny = curr.second + dy[k];
    if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
    if (vis[nx][ny]) continue;
    if (picture[nx][ny] != currColor) continue;
    areaSize++; vis[nx][ny] = true;
    q.push({ nx, ny });
}

 

 위와 같이 dx, dy 배열을 만들어 현재 영역에서 다음에 이동할 좌표를 구할 수 있다. 상하좌우 4개의 공간으로만 이동하기 때문의 크기가 4인 배열을 생성하고, 현재 좌표(curr 변수)에 for문을 이용하여 좌표의 x값에는 dx[i]를, y값에는 dy[i]를 더해주면 해당 영역에서 상하좌우로 이동한 좌표가 구해진다. 이때 아래와 같은 예외처리를 해주면 중복처리없이 영역을 체크할 수 있다.

 

- 현재 좌표가 그림을 벗어난경우 예외처리 : if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;

- 현재 영역을 이미 방문했던 경우 예외처리 : if (vis[nx][ny]) continue;

- 현재 영역이 기존 영역(curr)과 다른 색인 경우 예외처리 : if (picture[nx][ny] != currColor) continue;

 

 위 3가지 조건을 만족한다면 기준 영역으로부터 방문하지 않은 같은 색깔인 영역이며, 해당 영역의 좌표를 Queue에 push하고 Queue가 empty상태가 될 때 까지 탐색을 반복하며 영역의 갯수를 더해주면 된다. 이렇게 나온 영역에, 기존 최대 영역값과 MAX 연산을 반복하면 전체 그림에서 최대 영역의 크기를 구할 수 있다.

 

2. 영역 갯수 구하기

최대 영역을 구할 때, 탐색을 시작하는 횟수를 카운트하면 영역의 갯수를 구할 수 있다. 현재 좌표가 '컬러가 있으면서 체크했던 영역이 아닌 경우'탐색이 시작되며, 이 때마다 변수 'number_of_area'에 1을 더해줌으로 전체 영역의 갯수를 구했다.

 

코드

#include <bits/stdc++.h>

using namespace std;

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    bool vis[102][102];
    int dx[4] = { 1, 0, -1, 0 };
    int dy[4] = { 0, 1, 0, -1 };
    memset(vis,false,sizeof(vis));
    
    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) {
            if (picture[i][j] == 0 || vis[i][j]) continue;
            int areaSize = 0, currColor = picture[i][j];
            queue<pair<int, int>> q;
            q.push({ i, j }); vis[i][j] = true;
            number_of_area++; areaSize++;
            
            while (!q.empty()) {
                auto curr = q.front(); q.pop();
                for (int k = 0; k < 4; ++k) {
                    int nx = curr.first + dx[k];
                    int ny = curr.second + dy[k];
                    if (nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
                    if (vis[nx][ny]) continue;
                    if (picture[nx][ny] != currColor) continue;
                    areaSize++; vis[nx][ny] = true;
                    q.push({ nx, ny });
                }
            }
            max_size_of_one_area = max(max_size_of_one_area, areaSize);
        }
    }
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    cout << number_of_area << ' ' << max_size_of_one_area;
    return answer;
}

 

 

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