[백준 2667] 단지번호붙이기 cpp

문제
정사각형 모양의 지도가 있다. 1은 집이 있는 곳을 0은 집이 없는 곳을 나타낸다. 이때 인접한 집을 단지로 정의한다. 인접한 집이란 상하좌우로 이동할 수 있는 다른 집이다. 지도에서 단지의 수를 출력하고 각 단지에서 집의 수를 오름차순으로 출력하라.

입력
첫째 줄에 지도의 크기 N(5 이상 25 이하)이 입력된다.
그다음 N 줄에는 N개의 0 또는 1이 입력된다.

출력
첫째 줄에 총 단지수를 출력
이후 오름차순으로 단지 내의 집의 개수를 한 줄씩 출력

---

접근

단지라고 하는 것은 인접한 집(1)이 모여있는 것이다. 여기서 인접의 조건은 나의 집에서 상하좌우에 있는 다른 집이다. 따라서 현재 어떠한 집에서 DFS를 실행하여 상하좌우를 탐색하고 집이 안 나올 때까지 탐색하도록 한다.

여기서 DFS를 실행한 수만큼 단지의 수가 된다. 또한 단지 내의 집을 카운트하기 위해 단지별로 번호를 붙여 구분하도록 한다.

 

구현

이때 NxN만큼의 맵을 입력받는다.

맵 내의 정보를 입력받을 때 각 줄에서 N개의 수가 공간없이 이어서 입력되기 때문에 scaf("%1d")를 통해 숫자 한 개씩 map에 저장하도록 하였다.

또한 입력받은 값에 -1을 해주어 집을 0으로 빈 공간을 -1로 표시하였는데 이는 집의 번호가 1번부터 채워지도록 하기 위해서 사용하였다. (다른 방법을 사용해도 된다.)

int  number = 0;
cin >> N;
for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
     	scanf("%1d", &map[i][j]);
     	map[i][j] -= 1;
		}
	}

 

2차원 배열을 탐색하면서 0일 때(집을 만나면) number(단지의 번호)를 증가시킨 후 DFS를 실행한다.

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0) {
				++number;
				DFS(i, j, number);
			}
		}
	}

 

DFS 함수는 다음과 같다.

입력된 위치에 단지번호를 입력한다. 이것은 나중에 단지 내의 집을 카운트하는 목적도 있지만 방문한 곳을 표시하는 효과도 있다. 

이후 상하좌우를 탐색하여 집인 곳을 또다시 DFS를 실행한다. DFS를 모두 실행하고 마친다면 단지 하나가 형성된다.

void DFS(int y, int x, int num) {
	map[y][x] = num;

	for (int d = 0; d < 4; d++) {
		int ny = y + dir[d][0];
		int nx = x + dir[d][1];
		if (RangeCheck(ny, nx) && (map[ny][nx] == 0)) {
			DFS(ny, nx, num);
		}
	}
}

 

이제 DFS를 모두 마쳤다면 맵을 탐색하여 단지 내의 집의 개수를 카운트한다. 현재 단지 번호는 1번부터 되어있기 때문에 (단지 번호-1)를 집의 개수를 담는 cnt배열에 담는다. 여기서 단지 번호-1은 인덱스가 된다.

이후 오름차순으로 정렬하여 단지의 개수와 단지 내의 집의 수를 오름차순으로 출력한다.

for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] > 0) {
				cnt[map[i][j] - 1]++;
			}
		}
	}

	sort(cnt, cnt + number);
	cout << number << endl;
	for (int i = 0; i < number; i++) {
		cout << cnt[i] << endl;
	}

---

전체 코드

#include <iostream>
#include<algorithm>
#include <vector>
#include<queue>

using namespace std;

const int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };

int N;
int map[25][25];
int cnt[400];

bool RangeCheck(int y, int x) {
	return (y >= 0 && y < N) && (x >= 0 && x < N);
}

void DFS(int y, int x, int num) {
	map[y][x] = num;

	for (int d = 0; d < 4; d++) {
		int ny = y + dir[d][0];
		int nx = x + dir[d][1];
		if (RangeCheck(ny, nx) && (map[ny][nx] == 0)) {
			DFS(ny, nx, num);
		}
	}
}
int main()
{
	int  number = 0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%1d", &map[i][j]);
			map[i][j] -= 1;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 0) {
				++number;
				DFS(i, j, number);
			}
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] > 0) {
				cnt[map[i][j] - 1]++;
			}
		}
	}

	sort(cnt, cnt + number);
	cout << number << endl;
	for (int i = 0; i < number; i++) {
		cout << cnt[i] << endl;
	}
	return 0;
}