단지번호붙이기 #2667 c++ 풀이

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

2667번: 단지번호붙이기

먼저, 그래프 탐색알고리즘에서 전에 풀었던 문제의 코드(미로탐색)를 이것저것 변형해보면서 정답에 가까워졌다.

bfs문제를 풀때는 

bfs를 구현하고 자료구조를 추가해가면서 문제를 푸는 것이 유리했다.

#include<iostream>
#include<string>
#include<map>
#include<queue>
using namespace std;


int graph[101][101];
int visited[101][101];
int ans[101][101];

int N, M;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int c = 1;

void bfs(int y, int x) {
	if (graph[y][x] == 0)return;
	if (visited[y][x] == 1)return; 
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));

	ans[y][x] = c;
	//visited[0][0] = 1;
	

	while (!q.empty()) {

		int y = q.front().first;
		int x = q.front().second;

		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				continue;
			if (graph[ny][nx] == 0)
				continue;
			if (graph[ny][nx] == 1 && visited[ny][nx] == 0)
			{
				ans[ny][nx] = c;
				q.push(make_pair(ny, nx));
				visited[ny][nx] = 1;
			}
		}
	}
	c++;

}
int main() {
	
	cin >> N;
	string temp;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		for (int j = 0; j < N; j++) {
			if (temp[j] == '0')
				graph[i][j] = 0;
			else
				graph[i][j] = 1;
		}
	}
	//for (int i = 1; i <= N; i++) {
	//	for (int j = 1; j <= M; j++) {
	//		cout << graph[i][j] << " ";
	//	}
	//	cout << endl;
	//}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			bfs(i, j);
	}
	//bfs();
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cout << ans[i][j]<< " ";
		cout << '\n';
	}
	return 0;
}

이렇게 구현했을때,

 

정답 출력이 완성되었다. 이제 이것을 그냥 답으로 활용하기만 하면 된다. 

단지의 수는 c를 그냥 출력하면 될것이고, 

 houses ++로 집 수를 구해주고 마지막 출력에 1을 빼주는 식으로 구현해보았다.

 

코드는 다음과 같다. //현재 틀렸다고 나오는데 고쳐보는 중 입니다.

#include<iostream>
#include<string>
#include<map>
#include<queue>
using namespace std;


int graph[101][101];
int visited[101][101];
int ans[101][101];

int N, M;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
int c = 1;
int houses = 0;
vector <int> h;

void bfs(int y, int x) {
	if (graph[y][x] == 0)return;
	if (visited[y][x] == 1)return; 
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));

	ans[y][x] = c;
	houses++;
	//visited[0][0] = 1;
	

	while (!q.empty()) {

		int y = q.front().first;
		int x = q.front().second;

		q.pop();
		
		for (int i = 0; i < 4; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (nx < 0 || nx >= N || ny < 0 || ny >= N)
				continue;
			if (graph[ny][nx] == 0)
				continue;
			if (graph[ny][nx] == 1 && visited[ny][nx] == 0)
			{
				ans[ny][nx] = c;
				houses++;
				q.push(make_pair(ny, nx));
				visited[ny][nx] = 1;
			}
		}
	}
	h.push_back(houses);
	houses = 0;
	c++;
}
int main() {
	
	cin >> N;
	string temp;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		for (int j = 0; j < N; j++) {
			if (temp[j] == '0')
				graph[i][j] = 0;
			else
				graph[i][j] = 1;
		}
	}
	//for (int i = 1; i <= N; i++) {
	//	for (int j = 1; j <= M; j++) {
	//		cout << graph[i][j] << " ";
	//	}
	//	cout << endl;
	//}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			bfs(i, j);
	}
	sort(h.begin(), h.end());
	
	cout << c-1 << endl;
	for (int i = 0; i < h.size(); i++)
		cout << h[i]-1 << endl;;
	//bfs();
	//for (int i = 0; i < N; i++) {
	//	for (int j = 0; j < N; j++)
	//		cout << ans[i][j]<< " ";
	//	cout << '\n';
	//}
	return 0;
}