2667번: 단지번호붙이기

Memo

로직 설명

• 지도 전체를 돌면서 '1'을 만나는 순간 dfs를 돌려 단지에 속하는 집의 수를 구하고 ans 벡터에 저장 후 정렬하여 출력합니다.
• visited체크를 통해 방문한 곳은 다시 방문하지 않습니다.

Code

제출 날짜

2021/06/06

메모리

2024 KB

시간

0 ms

#include <iostream>
#include <vector>
#include <algorithm>
#define endl "\\n"

int N;

int dy[4] = {0,0,1,-1};
int dx[4] = {1,-1,0,0};
char g_map[26][26];
bool visited[26][26];
std::vector<int> ans;

void io_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	io_faster();
	std::cin >> N;
	for (int i = 0 ; i < N ; i++)
		std::cin >> g_map[i];
}

void dfs(int y, int x, int &cnt)
{
	int ny,nx;

	for (int i = 0 ; i < 4 ; i++)
	{
		ny = y + dy[i];
		nx = x + dx[i];
		if (ny < 0 || ny >= N || nx < 0 || nx >= N || visited[ny][nx] || g_map[ny][nx] == '0')
			continue;
		visited[ny][nx] = 1;
		cnt+=1;
		dfs(ny, nx, cnt);
	}
}

void solve()
{
	int cnt;

	for (int i = 0 ; i < N ; i++)
		for (int j = 0 ; j < N ; j++)
			if (!visited[i][j] && g_map[i][j] == '1')
			{
				cnt = 1;
				visited[i][j] = 1;
				dfs(i, j, cnt);
				ans.push_back(cnt);
			}
}

void print_val()
{
	std::cout << ans.size() << endl;
	std::sort(ans.begin(), ans.end());
	for (size_t i = 0 ; i < ans.size() ; i++)
		std::cout << ans[i] << endl;
}

int main()
{
	input();
	solve();
	print_val();
	return (0);
}