'2667 단지번호붙이기'에 해당되는 글 1건

2667 단지번호붙이기

문제 해석

가로 세로 크기가 5에서 25사이의 정사작형 배열에서 1이 뭉쳐져있는 구역을 구하고, 각 구역에서 1이 몇개나 있는지 오름차순으로 출력하라는 문제입니다.

1이 상하좌우에 있다면 그것은 같은 그룹에 속합니다. 아래 사진을 보세요.

<그림 1>에서 1의 그룹은 새 개의 구역으로 <그림 2>로 표현될 수 있습니다. 1번 그룹, 2번 그룹, 3번 그룹이 있고, 각각의 그룹은 7, 8, 9개의 1이 뭉쳐져있는 것이죠. 

입력은 가로, 세로의 길이가 주어지고, 위의 그림처럼 띄어지지 않은 문자열형태로 넘어옵니다. 이렇게 말이죠.

출력은 그룹의 갯수와 각 그룹이 포함하고 있는 1의 개수를 오름차순으로 출력합니다. 

풀이

DFS(Depth First Search)를 이용하면 쉽게 풀 수 있습니다. 우선 입력이 불친절하게 들어오니까 이를 정수형 배열로 바꾸어줍니다. 제가 문자 배열은 왠만하면 사용하기 싫거든요.

scanf("%d", &n);
for (int i = 0; i < n; i++) {
	char line[MAX_N];
	scanf("%s", line);
	for (int j = 0; j < n; j++) 
		map[i][j] = line[j] - '0';
}

배열의 길이 n을 입력받은 후에 for루프를 n번 돌면서 문자 배열 line으로 배열의 한줄을 입력받습니다. 그 for문의 내부 for문에서는 map배열에 실제 입력을 시킵니다. 그래서 map에는 입력들을 정수형 배열로 입력됩니다.

int cnt = 0;
for (int i = 0; i < n; i++) 
	for (int j = 0; j < n; j++) 
		if (map[i][j] == 1) {
			groups[cnt]=dfs(i, j);
			cnt = cnt + 1;
		}

입력을 받았으면 map을 전부 이중for문으로 돌며 1이 있는 부분에서 멈춥니다. 1이 있는 부분에서 멈추게 되면 그 지점에서 dfs를 호출하는 것이죠. dfs가 몇번 호출이 되느냐에 따라서 cnt가 커지게 됩니다. 바로 cnt가 그룹의 전체 갯수를 나타냅니다.

groups에는 cnt라는 그룹에 몇개의 1이 포함이 되어있는지 저장됩니다.

dfs에서 무슨 동작을 할까요? 이 문제를 풀기위한 핵심인 dfs를 보도록합시다.

int dfs(int y, int x) {
	if (y < 0 || x < 0 || y >= n || x >= n || map[y][x] == 0) return 0;
	map[y][x] = 0;
	return 1 + dfs(y + 1, x) + dfs(y - 1, x)
		+dfs(y, x + 1) + dfs(y, x - 1);
}

dfs함수는 바로 위와 같이 정의되어 있습니다. y는 행, x는 열만을 인자로 받아들이고 있습니다. y나 x가 배열 범위 밖에 있다면 더이상 dfs를 호출하지 않습니다. 또는 map[y][x]가 0인 부분도 기저사례에 포함이 됩니다. 지금까지 말했던 것들이 첫번째 if문의 조건이 되겠네요.

배열 범위에 포함이 되어있으며 map[y][x]=1이라면 바로 그 지점을 0으로 바꿔줍니다. 왜 바꿔주냐면 더 이상 이 점을 방문할 필요가 없으니까요. 만약 map[y][x]=0이 없다면 이 프로그램은 영원히 끝나지 않을겁니다.

그 후에는 상(y-1)하(y+1)좌(x-1)우(x+1)에 dfs를 호출합니다. return에 1을 더해야만 최종 dfs에는 그룹의 1의 개수가 return됩니다.

printf("%d\n", cnt);
sort(groups, groups + cnt);
for (int i = 0; i < cnt; i++) 
	printf("%d\n",groups[i]);

이제 답은 전부 구했네요. cnt를 출력하고 오름차순으로 1의 개수를 출력하라 하였으니 정렬 후에 groups를 출력하면 됩니다.

아래는 전체코드입니다.

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;

#define MAX_N 26

int n;
int map[MAX_N][MAX_N];
int groups[MAX_N*MAX_N];
int dfs(int y, int x) {
	if (y < 0 || x < 0 || y >= n || x >= n || map[y][x] == 0) return 0;
	map[y][x] = 0;
	return 1 + dfs(y + 1, x) + dfs(y - 1, x)
		+dfs(y, x + 1) + dfs(y, x - 1);
}
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		char line[MAX_N];
		scanf("%s", line);
		for (int j = 0; j < n; j++) 
			map[i][j] = line[j] - '0';
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) 
		for (int j = 0; j < n; j++) 
			if (map[i][j] == 1) {
				groups[cnt]=dfs(i, j);
				cnt = cnt + 1;
			}
		
	
	printf("%d\n", cnt);
	sort(groups, groups + cnt);
	for (int i = 0; i < cnt; i++) 
		printf("%d\n",groups[i]);
	
	return 0;
}

dfs만 알면 그리 어렵지 않게 풀수 있는 문제였습니다.