[카카오코드 2017] 프로그래머스 카카오프렌즈 컬러링북

문제 링크 : https://programmers.co.kr/learn/challenges?selected_part_id=300

※ 추천 선행 알고리즘 : BFS

문제 설명

카카오 프렌즈 컬러링북

출판사의 편집자인 어피치는 네오에게 컬러링북에 들어갈 원화를 그려달라고 부탁하여 여러 장의 그림을 받았다. 여러 장의 그림을 난이도 순으로 컬러링북에 넣고 싶었던 어피치는 영역이 많으면 색칠하기가 까다로워 어려워진다는 사실을 발견하고 그림의 난이도를 영역의 수로 정의하였다. (영역이란 상하좌우로 연결된 같은 색상의 공간을 의미한다.)

그림에 몇 개의 영역이 있는지와 가장 큰 영역의 넓이는 얼마인지 계산하는 프로그램을 작성해보자.

위의 그림은 총 12개 영역으로 이루어져 있으며, 가장 넓은 영역은 어피치의 얼굴면으로 넓이는 120이다.

입력 형식

입력은 그림의 크기를 나타내는 m과 n, 그리고 그림을 나타내는 m × n크기의 2차원 배열 picture로 주어진다. 제한조건은 아래와 같다.

• 1 <= m, n <= 100
• picture의 원소는 0 이상 2^31 - 1 이하의 임의의 값이다.
• picture의 원소 중 값이 0인 경우는 색칠하지 않는 영역을 뜻한다.

출력 형식

리턴 타입은 원소가 두 개인 정수 배열이다. 그림에 몇 개의 영역이 있는지와 가장 큰 영역은 몇 칸으로 이루어져 있는지를 리턴한다.

예제 입출력

m	n	picture	answer
6	4	[[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]]	[4, 5]

Algorithm

같은 값을 가진 군집의 개수를 구하고, 가장 넓은 군집의 원소 개수를 구하시오.

1. 먼저 같은 값을 가졌는지 찾기 위해서는 기존에 있던 location 값과 옮겨졌을 때의 location과 같은지 비교 후 같다면 +1씩 늘려나가면 된다.

입력 예제를 통해 예를 들면

1 1 1 0

1 2 2 0

1 0 0 1

0 0 0 1

0 0 0 3

0 0 0 3

빨간색 1에서 시작하였을 때 파란식 1을 찾는 것인데, 기존의 location값이 빨간색 1이라면

아래 1 -> 아래 1

오른쪽 1 -> 오른쪽 1

이런식으로 모든 경우의 수를 다 찾다가 다른 수(즉, 군집이 끊겼을 때)를 만나면 +0을 함과 동시에 찾는 것을 그만하면 된다.

2. 예외처리가 있다면, 다음과 같다. 

 1) x축과 y축이 m과 n을 벗어 났을 때

 2) 기존의 location값과 옮겨진 location이 같지 않을 때

즉, 다음과 같은 예외 사항들은 +0 처리를 해주고 찾는 것을 종료하는 사항들이다.

3. 또한 들린 구간은 0으로 처리하여 중복 군집을 더 이상 찾지 않도록(찾았던 군집을 또 찾는 현상)) 해준다.

4. 1~3 알고리즘을 토대로 max_size_of_one_area 값을 비교하며 걸러내면 

1 1 1

1

1

의 군집에서 5개의 원소를 가진 군집을 max_size_of_one_area 값으로 갖게된다.

5. 또한 3번 알고리즘에서 중복 방지를 위해 걸러낸 부분을 하나씩 세게된다면 4개의 군집을 찾는다.

따라서, vector answer의 값은 4 5를 갖게 된다.

6. 1~3을 모두 처리한 알고리즘을 소스코드로 보면 다음과 같다.

//kuklife.tistory.com #include <vector> using namespace std; int allsum(int location, int m, int n, int x, int y, vector<vector<int>> &picture) { int sum = 1; if (x >= m || y >= n || x<0 || y<0 || picture[x][y] != location) return 0; else { picture[x][y] = 0;//들렸으니 0 처리 sum += allsum(location, m, n, x + 1, y, picture); // 오른 sum += allsum(location, m, n, x, y + 1, picture); // 위 sum += allsum(location, m, n, x - 1, y, picture); // 왼 sum += allsum(location, m, n, x, y - 1, picture); // 아래 } return sum; } vector<int> solution(int m, int n, vector<vector<int>> picture) { int number_of_area = 0; int max_size_of_one_area = 0; int sum = 0; vector<int> answer(2); //auto temp = picture; for (int i = 0; i<m; i++) { for (int j = 0; j<n; j++) { if (!picture[i][j]) continue; else { sum = allsum(picture[i][j], m, n, i, j, picture); number_of_area++; if (sum > max_size_of_one_area) max_size_of_one_area = sum; } } } answer[0] = number_of_area; answer[1] = max_size_of_one_area; return answer; }

7. BFS 방식도 가능하지만, 미로찾기가 아니고 군집을 찾아내는 것이니 위의 소스코드가 계산적인 측면해서 조금 더 편하다고 생각된다. BFS 사용하였을 땐, 소스코드는 다음과 같다.

//kuklife.tistory.com #include <vector> #include <queue> using namespace std; vector<int> solution(int m, int n, vector<vector<int>> picture) { int number_of_area = 0; int max_size_of_one_area = 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) continue; int color = picture[i][j]; picture[i][j] = -color; number_of_area++; queue<pair<int, int>> q; int size = 1; 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) && (ny >= 0) && (nx < m) && (ny < n) && (picture[nx][ny] == color)) { picture[nx][ny] = -color; size++; q.push(make_pair(nx, ny)); } } } if (max_size_of_one_area < size) max_size_of_one_area = size; } } vector<int> answer(2); answer[0] = number_of_area; answer[1] = max_size_of_one_area; return answer; }