카카오프렌즈 컬러링북(프로그래머스)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/1829

프로그래머스

탐색 문제이다.

 

탐색 알고리즘 개념을 알고 있다면 굉장히 쉬운 문제이고, 모른다면 어려운 문제일 것이다.

 

 

문제에서 2차원 배열을 주고 영역의 개수와 영역의 넓이를 구하라고 했는데 이런 문제는 거의 탐색 기법으로 풀린다.

 

가장 기초적이면서 제일 잘 나오는 탐색 알고리즘은 DFS(백트래킹은 DFS와 거의 동일)와 BFS이다.

 

위의 문제는 두 알고리즘 중 아무거나 사용해도 무방하다.

(단, 최단경로 문제일 경우 DFS를 사용하면 시간초과가 날 수 있다.)

 

 

나는 DFS로 풀었다.

 

BFS로 코딩하라면 하겠지만, DFS가 좀 더 쉽게 구현이 가능하다.

 

그 이유는, DFS는 재귀를 이용해서 구현할 수 있기 때문이다!!

 

 

푼 방식을 예를 들어 설명한다면

 

1 1 1 0

1 2 2 0

1 0 0 1                         왼쪽에 6 X 4 모양의 2차원 배열이 입력으로 주어졌다고 하자.

0 0 0 1                         

0 0 0 3                         영역의 개수와 영역의 최대넓이를 구하는 것이 목표라고 하였다.

0 0 0 3

 

머리로 계산하면 영역의 개수는 4개, 최대 영역의 넓이는 5라는 것을 알 수 있다.

 

이것을 코드로 작성하려면 배열의 [0][0] 부터 순차적으로 탐색하며

 

0이 아닌 숫자가 나올 경우 그 부분부터 DFS 알고리즘을 이용하여 계산한다.(문제에서 0은 색칠하지 않은 부분이라고 명시함.)

 

이를 간단히 코드로 나타내면

 

for i = 0 to m

  for j = 0 to n

    if picture[i][j] != 0

      DFS()

 

이렇게 되겠다.

 

 

그렇다면 DFS는 어떻게 구현할까?

 

먼저 위의 [0][0] 부분을 보면 1이라는 값이 있다.

 

0이 아니므로 저 부분에서 상,하,좌,우 4가지 방향을 탐색한다.(문제에서 상하좌우만 포함한다고 설명함.)

 

위와 왼쪽은 인덱스가 없으므로 건너뛰고 아래와 오른쪽을 탐색한다.

 

먼저 오른쪽을 보면 이전의 값과 같은 값이 존재하므로 다시 DFS 알고리즘을 실행한다.

 

그 다음 아래 부분도 마찬가지로 이전의 값과 같으므로 다시 DFS 알고리즘을 실행한다.

 

 

 

그런데 여기서 중요한 부분이 있다.

 

우리는 [0][0]에서 시작해서 오른쪽인 [0][1]에서 다시 DFS를 진행했는데,

 

오른쪽 관점에서 왼쪽은 이미 이전에 진행했던 부분이다.

 

그러므로 반드시 DFS 탐색이 진행되면 해당 부분을 0으로 만들어 줘서 불필요한 계산을 줄여야 한다.

 

그래야지만 속도도 빨라지고 영역의 넓이도 올바르게 구할 수 있다.

 

 

아래는 내가 짠 코드이다.

 

#include <vector>
 
#define MAX(a, b) ((a) > (b) ? (a) : (b))
 
using namespace std;
 
int exM, exN;
int tempArea = 0; //임시로 쓰일 영역의 넓이
int range[4][2] = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}}; //이동 범위(상, 하, 좌, 우)
 
int board[100][100] = {0, };
 
bool rangeCheck(int row, int column) {
    if (row >= 0 && row < exM && column >= 0 && column < exN) {
        return true;
    }
    
    return false;
}
 
void DFS(int x, int y, int data) {
    ++tempArea;
    board[x][y] = 0;
    
    for (int i = 0; i < 4; i++) {
        int dx = x + range[i][0];
        int dy = y + range[i][1];
        
        if (rangeCheck(dx, dy) && board[dx][dy] == data) {
            DFS(dx, dy, data);
        }
    }
}
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
vector<int> solution(int m, int n, vector<vector<int>> picture) {
    int number_of_area = 0; //영역의 수
    int max_size_of_one_area = 0; //가장 큰 영역의 넓이
    
    exM = m;
    exN = n;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = picture[i][j];
        }
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j] != 0) {
                DFS(i, j, board[i][j]);
                max_size_of_one_area = MAX(tempArea, max_size_of_one_area);
                tempArea = 0;
                ++number_of_area;
            }
        }
    }
    
    
    
    vector<int> answer(2);
    answer[0] = number_of_area;
    answer[1] = max_size_of_one_area;
    return answer;
}