1번.md

Title : [ 카카오프렌즈 컬러링북 ]
Tag : FloodFill, Stack, 미로찾기

알고리즘 이론 :

Flood Fill

---

예시 :

stack 기본 함수

추가 및 삭제

• push(element) : top에 원소를 추가
• pop() : top에 있는 원소를 삭제

조회

• top() : top(스택의 처음이 아닌 가장 끝)에 있는 원소를 반환

기타

• empty() : 스택이 비어있으면 true 아니면 false를 반환
• size() : 스택 사이즈를 반환

문제 :

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

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

입력 :

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

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

출력 :

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

답 :

// Flood Feel

#include stdio.h
#include stdlib.h
#include stack

using namespace std;

class point {
private:
	int x, y;

public:
	point(int x, int y) {
		this->x = x;
		this->y = y;
	}
	int getX() {
		return x;
	}
	int getY() {
		return y;
	}
};

int main() {

	int m = 6, n = 4;
	int c_idx = 0, r_idx = 0;
	stack s;
	int color = 0;
	int num = 0;
	int scale = 0, max_scale = 0;
	int control = 1;

	int map[6][4] = { 0 }; //0은 방문 안 한 상태
	int picture[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}
	};

	map[0][0] = 1;

	for (int i = 0; i < m; i++) {

		for (int j = 0; j < n; j++) {

			c_idx = i;
			r_idx = j;

			if (picture[i][j] != 0) {
				control = 0;

				/* 초기화 작업 */
				if ((i == 0 && j == 0 ) || map[c_idx][r_idx] == 0) { //0 방문 안 했다면
					color = picture[c_idx][r_idx]; //현재 컬러 저장
					scale = 1;
					num++;
				}
			}

			//방문했고 control 1 이면 나옴
			while ( map[c_idx][r_idx] == 0 || control == 0 ) {

				/* 갈 수 있는 경우의 수를 push */
				if (color == picture[c_idx][r_idx - 1] && map[c_idx][r_idx - 1] == 0) { //상
					s.push(point(c_idx, r_idx -1));
				}
				if (color == picture[c_idx][r_idx + 1] && map[c_idx][r_idx + 1] == 0) { //하
					s.push(point(c_idx, r_idx + 1));
				}
				if (color == picture[c_idx - 1][r_idx] && map[c_idx - 1][r_idx ] == 0) { //좌
					s.push(point(c_idx -1, r_idx));
				}
				if (color == picture[c_idx + 1][r_idx] && map[c_idx + 1][r_idx] == 0) { //우
					s.push(point(c_idx + 1, r_idx));
				}

				if (s.empty() == true) { //stack이 비었으면 나옴
					control = 1;
					break;
				}

				/* 방문 */
				point p = s.top();
				s.pop();
				c_idx = p.getX();
				r_idx = p.getY();
				map[c_idx][r_idx] = 1;
				scale++;
				if (max_scale < scale)
					max_scale = scale;
				/* pop 하면 그 위치를 방문한 것이니
				그 자리에서 다시 갈 수 있는 경우의 수를 찾아야 함 */
			}
		}
	}

	printf("%d %d \n", num, max_scale);
}

---

링크

• http://tech.kakao.com/2017/08/11/code-festival-round-1/