[프로그래머스]2017 카카오코드 예선 : 카카오프렌즈 컬러링북 (level 2)(c++)

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

프로그래머스

 

방법 1: DFS

#include <vector>
#include <algorithm>

using namespace std;

int M, N;
// 오른쪽, 아래쪽, 왼쪽, 위쪽
vector<pair<int, int>> drx = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

void dfs(vector<vector<int>> &picture, vector<int> &cnt, int x, int y)
{
    // 해당 색 영역 개수 + 1
    ++*(cnt.end() - 1);
    int num = picture[x][y];
    
    // 한번 지나간 영역은 0으로 바꾸기
    picture[x][y] = 0;

    // 현재 (x, y)칸과 같은 색의 영역이 있는지 4 방향으로 탐색 
    for (int k = 0; k < 4; ++k)
    {
        int newX = x + drx[k].first;
        int newY = y + drx[k].second;
        
        if (newX >= 0 && newX < M && newY >= 0 && newY < N && num == picture[newX][newY])
        {
            // 다음 영역의 4방향 탐색을 위해 dfs 재귀호출
            dfs(picture, cnt, newX, newY);
        }
    }
}

vector<int> solution(int m, int n, vector<vector<int>> picture) {
    
    M = m;
    N = n;
    vector<int> cnt;

    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            // 색칠된 "새로운" 영역이 있으면 같은 색 영역 탐색 시작
            if (picture[i][j] > 0)
            {
                cnt.push_back(0);
                dfs(picture, cnt, i, j);
            }
        }
    }

    vector<int> answer(2);
    answer[0] = cnt.size();
    answer[1] = *max_element(cnt.begin(), cnt.end());

    return answer;
}

 

방법 2: BFS

#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<int> solution(int m, int n, vector<vector<int>> picture) {

    // 오른쪽, 아래쪽, 왼쪽, 위쪽
    vector<pair<int, int>> drx = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

    vector<int> cnt;
    queue<pair<int, int>> q;
    vector<vector<bool>> visited(m, vector<bool>(n));

    for (int i = 0; i < m; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            // 색칠된 "새로운" 영역이 있으면 같은 색 영역 탐색 시작
            if (!visited[i][j] && picture[i][j] > 0)
            {
                cnt.push_back(0);
                q.push(make_pair(i, j));
                visited[i][j] = true;

                while (!q.empty())
                {
                    // 이번 차례 영역값 저장 후 queue.pop
                    int x = q.front().first;
                    int y = q.front().second;
                    int num = picture[x][y];
                    
                    q.pop();
                    printf("x : %d  y : %d   color : %d\n", x, y, num);

                    // 해당 색 영역 개수 + 1
                    ++* (cnt.end() - 1);

                    // 색이 같은 인접 영역을 4 방향으로 탐색 
                    for (int k = 0; k < 4; ++k)
                    {
                        int newX = x + drx[k].first;
                        int newY = y + drx[k].second;

                        // 아직 방문하지 않고, 색이 같은 인접영역을 찾으면 queue에 push
                        if (newX >= 0 && newX < m && newY >= 0 && newY < n 
                            && !visited[newX][newY] && num == picture[newX][newY])
                        {
                            q.push(make_pair(newX, newY));
                            visited[newX][newY] = true;
                        }
                    }
                }
            }
        }
    }

    vector<int> answer(2);
    answer[0] = cnt.size();
    answer[1] = *max_element(cnt.begin(), cnt.end());

    return answer;
}

 

BFS는 대개 DFS보다 느리다

 

 

 

TIP1

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.

이 문제는 위와 같이, 이유를 알 수 없는 조건이 하나 더 있다ㅋㅋ

전역변수를 최대한 줄이는게 속 편하다.

 

 

TIP2

방향 문제는 상대 위치값으로 해치우자

// 오른쪽, 아래쪽, 왼쪽, 위쪽
vector<pair<int, int>> drx = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };

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

 편한대로 골라서 하면 된다.

한번 알고 나면 계속 써먹게 되는 방향 인덱스..

 

 

TIP3

DFS의 경우는 필요없지만, BFS는 visited[][]배열이 필요하다.

DFS 풀이에서는 지나간 picture[x][y]의 값을 0으로 바꿔주었다.

하지만 이는 재귀호출을 하면서, 해당 시점의 색깔값이 기억되기 때문에 괜찮은 것이다.

 

BFS에서 원본 picture값을 바꿔가면서 진행하면, 어떤 문제가 생기는지 살펴보자

편의상 색깔 값을 A로 설정했다. 방향은 오른->아래->왼->위 순이다

picture과 방향 배열이 이렇게 생겼다고 하자.

우리는 큐에 "현재 영역과 같은 색깔을 가진 인접 영역"을 push할 것이다.

그리고 pop할때에는 해당 영역 값을 0으로 바꿀 것이다.

 

 

음 아직까지 순조롭다

 

큐에 저장된 영역이 pop할때, 해당 색깔과 같은 색을 가진 영역을 push한다

pic[0][0]은 pop 하면서 pic[0][1] 과 pic[1][0]을 push한다

pic[0][0]은 이제 0이다.

 

 

아직까지도 괜찮은데, picture[1][1]을 주의하자

pic[0][1]이 pop할 차례가 되면

pic[0][2]과 pic[1][1]을 push한다.

pic[0][1]은 이제 0이다.

 

똑같은 영역이 큐에 2번 들어왔다. 그런데 이게 무슨 문제가 되나?

pic[1][0]이 pop할 차례가 되면

pic[1][1]을 push 한다?!

pic[1][0]은 이제 0이다.

 

이런 문제가 된다.

 

첫번째 pic[1][1]이 pop할 차례가 되면, pic[1][1]은 이제 0이다.

그렇게 되면 2번째 pic[1][1]은 자신(=0)과 같은 영역을 찾아서 큐에 push하게 된다.

문제 발생 확인!

 

따라서 BFS로 구현할때에는 원본 picture값을 건드리지 않는 것이 좋다.

원본값 변경하면서 구현하시는 분 더 좋은 아이디어가 있으면 댓글 부탁드립니다,,,

 

 

 

TIP4

문제에서 서로 떨어진 같은 숫자영역은 서로 다른값으로 취급하고 있다.

따라서 영역 한뭉치를 만날 때마다 새로운 갯수요소를 push해주는게 효율적이다.

// 색칠된 "새로운" 영역이 있으면 같은 색 영역 탐색 시작
if (picture[i][j] > 0)
{
	cnt.push_back(0);
}


...


// 해당 색 영역 개수 + 1
++*(cnt.end() - 1);