[C/C++] 코드업(codeup) 4421번 단지 번호 붙이기

▽문제 바로가기

https://codeup.kr/problem.php?id=4421

단지 번호 붙이기

---

입력

첫 번째 줄에는 지도의 크기 N(정사각형으므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고,

그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

 

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

 

문제 풀이

 

그림판 채우기 문제나 전광판 전구 조작 문제와 매우 유사합니다.

 

https://swblossom.tistory.com/89

[C/C++] 코드업(codeup) 4060번 전광판 전구 조작

https://swblossom.tistory.com/83

[C/C++] 코드업(codeup) 2610번 그림판 채우기

집이 있다면 이웃한 동서남북으로 탐색하면서 카운트하면 됩니다. 집 개수를 벡터에 저장했다가 나중에 정렬 후 출력하면 끝.

 

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int n;
char arr[26][26];
int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};

//전구를 켜는 함수
int recur(int row, int col){
	//범위 밖이면 리턴
	if(row==-1||col==-1||row==n||col==n) return 0;
	
	//집이 없으면 리턴
	if(arr[row][col]=='0') return 0;
	
	//집이 있으면 집갯수1더하고 동서남북으로 탐색하고 
	arr[row][col] = '0';
	return 1 + recur(row+dy[0], col+dx[0]) + recur(row+dy[1], col+dx[1])
			+ recur(row+dy[2], col+dx[2]) + recur(row+dy[3], col+dx[3]);
	
}

int main(){
	
	scanf("%d", &n);
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin >> arr[i][j];
		}
	}
	
	int cnt = 0;
	vector <int> v;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(arr[i][j]=='1') {v.push_back(recur(i, j)); cnt++;}	//집이있다면 단지를 정의하고 갯수세기
		}
	}
	
	sort(v.begin(), v.end());
	
	printf("%d\n", cnt);
	for(int i=0;i<v.size();i++) printf("%d\n", v[i]);
	
	return 0;
}