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

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

2667번: 단지번호붙이기

 

DFS로 풀 수 있다. 

 

전체 그래프를 traverse하면서 1인 것 찾아서, 연결된 노드들을 0으로 바꿔주면서(dfs이용) count한다. = 단지 1개. 이게 하나의 단지니까 num_blocks에 1을 증가시킨다. 이 dfs를 하면서 단지 내에 건물 수를 센 게 count인데, 이걸 vector에 넣어서 나중에 한번에 출력할 수 있도록 한다. 

그리고 다음으로 다른 단지를 생성할 1인 것을 찾고, 거기서부터 또 연결된 노드들을 0으로 바꿔주면서 위와 같은 과정을 거친다. 

and so on...

 

그러면 최종적으로 count에는 단지의 개수가 저장된다.

vector에는 각 단지별 건물 수가 저장되어 있다. 

 

오름차순으로 출력하라고 했으니까 vector을 sort해준다.

 

그리고 num_blocks 와 vector 요소들을 출력해주면 완성.

 

* 주의할 점은 주변에 근접한 노드를 찾을 때, 범위 확인을 해줘야 한다는 점. 

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

using namespace std;

int map[25][25];
int n;

int dfs(int x, int y){
	
	int count = 0;
    // 방향 벡터
	int move_x[4] = {-1, 1, 0, 0};
	int move_y[4] = {0, 0, -1, 1};
	
	map[x][y] = 0;
	count++;
	
	for(int i=0; i<4; i++){
		int newx = x + move_x[i];
		int newy = y + move_y[i];
		
		if(newx>=0 && newx<n && newy>=0 && newy<n && map[newx][newy]==1){
        // 이웃 좌표가 범위를 넘어서지 않는지 확인할 필요가 있다. 
			count += dfs(newx, newy);
		}
	}
	
	return count;
}

int main(void){
	
	cin >> n;
	
	for(int i = 0; i<n; i++){
		string str;
		cin >> str;
		
		for(int j = 0; j<n; j++){
			map[i][j] = str[j]-'0';
		}
	}
	
	int num_blocks=0;
	vector<int> answer;
	for(int i = 0; i<n; i++){
		for(int j = 0; j<n; j++){
			if(map[i][j] == 1){
				answer.push_back(dfs(i, j));
				num_blocks++;
			}
		}
	}
	
	sort(answer.begin(), answer.end());
	cout << num_blocks << endl;
	for(int i =0; i<answer.size(); i++){
		cout << answer[i] << endl;
	}
}