[백준 2567] 색종이-2

https://www.acmicpc.net/problem/2567

2567번: 색종이 - 2

#include <stdio.h>
int n;
int paper[100 + 2][2 + 2];
int board[100 + 2][100 + 2];

int dir_x[4] = { -1, 1, 0, 0 }; //udlr
int dir_y[4] = { 0, 0, -1, 1 };

int total;

void input(void)
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d %d", &paper[i][0], &paper[i][1]);
	}
}

void fill_board(void)
{
	for (int k = 0; k < n; k++) {
		int x = paper[k][0];
		int y = paper[k][1];
		for (int i = x; i < (x + 10); i++) {
			for (int j = y; j < (y + 10); j++) {
				board[i][j] = 1;
			}
		}
	}
}


int check_fill(int x, int y)
{
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
		int nx = x + dir_x[i];
		int ny = y + dir_y[i];
		if (board[nx][ny] == 0) cnt++;
		else continue;
	}
	return cnt;
}


void get_len(void)
{
	for (int i = 1; i < 101; i++) {
		for (int j = 1; j < 101; j++) {
			if (board[i][j] == 1) total += check_fill(i, j);
		}
	}
	return;
}

int main(void)
{
	input();
	fill_board();
	get_len();
	printf("%d", total);
	return 0;
}

이문제도 사실 처음에 아이디어 생각하기 어려웠다.

근데 앞으로 이런 류의 문제는 일단 전역변수로 int board[100 + 2][100 + 2]; 초기화 시켜놓고, 해당 범위이면 1을 채워서 탐색해야 겠다고 생각했다. 

 

//fill_board 함수

이 문제는 도형을 가지고 어떻게 하는게 아니라, 입력받은 좌표를 가지고 색종이부분은 1로 채우고 나머지는 0으로 두어 둘레를 계산해야 쉽게 풀린다. 

 

 //check_fill 함수     //get_len 함수

둘레는 만약 내가 지금 있는 좌표가 1일때 (색종이 부분) 상, 하, 좌, 우를 살펴봐서 0이면 가장 바깥쪽 부분이므로 cnt++;을 해준다. 

 

 

예시로 fill_board 함수를 돌려서 0과 1이 채워진 board의 모습을 출력하면 다음과 같다. 

//input
4
3 7
5 2
15 7
13 14

//output
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

이렇게 보면 명확하게 0과 인접해있는 1의 위치에서 cnt++을 해주어야 둘레가 구해진다는 것을 알 수 있다.