백준 BOJ 1926 - 그림

지난번에 풀었던 단지번호매기기? 문제랑 비슷해서 건드렸는데

의외로 고민했으나 고민한 이유가 매우 의미읎는것이었다.

​

재귀함수짜는데 fill함수 앞에 return을 붙여놔서 방향이 여러갈래로 나뉠때 탐색을 제대로 못했기 때문이었다 ㅠ

return만 떼니 AC.

 

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

1926번: 그림

항상 프로그래밍을 하면서 하는 생각 중의 하나인데,

프로그래밍을 할때 보수적으로 문제해결하는게 아무래도 굉장히 안 좋은 행위라고 나는 생각한다.

​

지금 이 문제를 풀때도 습관적으로 그냥 재귀함수가지고 적당히 채워가면서 풀었지만,

이 문제는 원래 BFS를 사용해서 푸는게 정석에 가깝다고 한다.

​

지금처럼 꼼수에 가깝게 푸는 것이 올바르지 못한 행동은 아니지만서도,

정보분야는 굉장히 발전이 빠르다는걸 생각해보면 내가 이렇게 익숙한것으로만 풀기에

상대적으로 뒤쳐지는것이 아닌가 하는 생각이 든다.

#include <stdio.h>

int map[1000][1000] = {0};
int piccount=0;
int picarea=0; 
int tmp=0;

int fill(int x, int y){
	map[x][y] = 0;
	tmp++;
	if(map[x+1][y] == 1) fill(x+1,y);
	if(map[x-1][y] == 1) fill(x-1,y);
	if(map[x][y+1] == 1) fill(x,y+1);
	if(map[x][y-1] == 1) fill(x,y-1);
	return 1;
}

int main(){
	int n,m;
	scanf("%d %d", &n, &m);
	for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) scanf("%d", &map[i][j]);
	
	for(int i=1; i<=n; i++){
		for(int j=1; j<=m; j++){
			if(map[i][j] != 0){
				tmp=0;
				piccount++;
				fill(i,j);
				if(tmp > picarea) picarea = tmp;
			}
		}
	}
	
	printf("%d\n%d", piccount, picarea);
	return 0;
}

소스코드에 대해서 간단히 설명하자면,

그림의 개수를 셀 때에는, 근접해있는 부분의 그림을 아예 안그려진 것으로 변경해서 중복으로 세지 않도록 했고,

그림의 크기는 안그려진것으로 변경할때 카운터를 하나씩 올려주면 된다.

​

문제 자체는 어렵지 않았으나 어렵지 않았기에 많은 생각을 해보게 하는 문제였다.

마치 수학에서 곱셈숙제를 냈더니 전부 더해서 푸는 기분이랄까.