개요

백준 2667번: 단지번호 붙이기

• 입력
  첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

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

접근 방법

1. 백준 1743(음식물 피하기) 문제와 같다.
   1743문제에서는 각 컴퍼넌트의 노드 갯수를 다 비교해서 가장 큰 값을 출력하지만,
   이 문제에서는 각 컴퍼넌트의 크기를 정렬해서 출력하는 문제다.

2. 벡터로 컴퍼넌트 크기 저장 후 오름차순으로 정렬하였다,

코드

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

using namespace std;
int N = 0;
int realEstate[26][26];
bool visited[26][26];
int dx[4] = {-1,1,0,0};
int dy[4] = {0,0,-1,1};
vector<int> Ans;

void input() {
	string row = "";
	cin >> N;
	//숫자로 한줄 입력해온후 나머지연산으로 하나씩 일일이 넣어주기
	for (int i = 0; i < N; i++) {
		int cnt = 0;
		cin >> row;
		for (int j = 0; j < N; j++) {
			realEstate[i][j] = row[j]-'0';
		}
	}
}

int dfs(int x, int y) {
	//이미 방문한 곳이라면 return 0
	if (visited[x][y]) return 0;
	//방문했다,
	visited[x][y] = true;
	//return할 노드. 기본적으로 x,y가 있으므로 1 
	int Node=1;
	for (int i = 0; i < 4; i++) {
		int nextA = x+ dx[i];
		int nextB = y+ dy[i];
		//만약 x,y좌표의 상하좌우 각각의 값이 범위를 넘지않으면서 집이 있는 곳이라면
		if (nextA >= 0 && nextB >= 0 && nextA < N && nextB < N && realEstate[nextA][nextB]) {
			//방문도 안했던곳이면
			if (!visited[nextA][nextB]) {
				//dfs재귀를 돌려서 해당칸으로 갔을때의 노드 수 반환하여 합침
				Node += dfs(nextA, nextB);
			}
		}
	}
	return Node;
}

void solution() {
	//컴퍼넌트 갯수 
	int components=0;
	//방문한곳 false로 처리
	fill(&visited[0][0], & visited[25][25], false);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			//방문하지 않았고, 단지가 존재한다면
			if (!visited[i][j] && realEstate[i][j]) {
				//새로운 단지 있는것이므로 compoenent 추가
				components++;
				//컴퍼넌트가 몇개있을지 모르므로 벡터에 push
				Ans.push_back(dfs(i, j));
			}
		}
	}
	//컴퍼넌트 갯수 출력
	cout << components<<'\n';
	//오름차순으로 출력하라했으므로 정렬
	sort(Ans.begin(),Ans.end());
	//벡터 iterator로 원소들 다 출력
	for (auto iter = Ans.begin(); iter != Ans.end(); ++iter) {
		cout << *iter << '\n';
	}
}

int main() {
	input();
	solution();
}

문풀후생

	int Node=1;
	for (int i = 0; i < 4; i++) {
		int nextA = x+ dx[i];

dfs함수의 위 부분에서 nextA를 바보같이 반복문 밖에 선언한후
반복문 안에 nextA+=dx[i]라고 적어버려서 nextA가 초기화가 안되고
게속 더해져나가서 오답이 나왔다..

상하좌우를 비교하면서 컴퍼넌트 구해나가는 문제를
세문제정도 풀어보니 자신이 좀 생겼다!