논리문제, 덧칠하기

문제

N*N 크기의 도화지에 1~9의 색을 칠한다. 이때 직사각형 모양으로 색칠한다. 매번 다른색을 칠하며

영역을 완전히 침범하지 않는 선에서 덧칠을 할 수 있다. 이때 덧칠되지 않은 색은 몇개인지 구하라.

 

input (도화지 크기, 색정보)

4

1230

1737

1777

0220

 

output

2

 

접근방법

1. 색영역은 무조건 직사각형이다. 색 영역의 min, max 꼭지점 좌표를 구한다.

2. 색영역을 탐색하며 해당 색 영역에 침범된 다른 색을 Checker 배열에 count한다.

3. Checker배열에서 다른 영역을 침범하지 않은 색의 갯수를 구한다.

 

 

 

#include <stdio.h>

int N;
char paint[12][12];

void input(){
	scanf("%d",&N);
	
	for(int i=0; i<N; i++)
	{
		scanf("%s", &paint[i]);
	}
}

int main() {
	input();
	/*
	printf("%d\n",N);
	
	for(int i =0; i<N; i++)
	{
		printf("%s\n",paint[i]);
	}
	*/
	//좌표찾기
	int answer=0;
	int minR, minC,maxR, maxC, R, C=0;
	int color=0;
	int checker[12]={0,};
	for(color=1; color<=9; color++){
		minR = minC = 10;
		maxR = maxC = 0;
		
		for(R=0; R<N; R++){ //탐색
			for(C=0; C<N; C++){
				if(paint[R][C] == (color+'0')){
					//printf("color : %d _ R : %d _ C : %d)\n",color,R,C);			
					if(minR > R) minR=R;
					if(maxR < R) maxR=R;
					if(minC > C) minC=C;
					if(maxC < C) maxC=C;
				}
			}
		}
		if(minR==10) continue;
		//printf("color : %d _ min(%d,%d) _ max(%d,%d)\n",color,minR,minC,maxR,maxC);
		//color 새기
		checker[color]++;
		for(R=minR; R<=maxR; R++){
			for(C=minC; C<=maxC; C++){
				if(paint[R][C] != color + '0'){
					//printf("color : %d _ R : %d _ C : %d)\n",color,R,C);			
					checker[paint[R][C]-'0']++;
				}
			}
		}
	}
	/*
	for(int i=1; i<12; i++){
		printf("%d  ", checker[i]);
	}
	printf("\n");
	*/
	for(int i=1; i<12; i++){
		if(checker[i]==1) answer++;
	}
	
	printf("%d", answer);
	
	return 0;
}