백준 / 바킹독님의 문제집 / 단지 번호 붙이기(2667)

문제 설명

 

 

문제 해결

 

테스트 케이스를 하나 더 늘렸다.

 

4 4

0101

1010

0101

1010

 

잘못된 결과가 나와서 코드를 삼항 연산자를 이용하여 살짝 수정했다.

 

#include <iostream>
#include <queue>
#include <utility>
#include <tuple>
#include <string>
#include <vector>
#include <algorithm>

#define x first
#define y second

using namespace std;

queue<pair<int, int>> q;
pair<int, int> direction[4] = { make_pair(1,0),make_pair(0,1), make_pair(-1,0), make_pair(0,-1) };
vector<int> house_count_list;

int map[30][30];
int visit[30][30]{ 0 };
int apt_comp_count = 0;
int N;

int main(int argc, char* argv[])
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);


	cin >> N;

	string input;
	for (int i = 0; i < N; i++)
	{
		cin >> input;
		for (int j = 0; j < N; j++)
			map[i][j] = input[j] - '0';
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (map[i][j] == 1 && visit[i][j] == 0)
			{
				apt_comp_count += 1;
				q.push(make_pair(i, j));
				int house_count = 0;
				while (!q.empty())
				{
					house_count += 1;
					auto current = q.front();
					q.pop();

					for (int i = 0; i < 4; i++)
					{
						int nx = current.x + direction[i].x;
						int ny = current.y + direction[i].y;

						if (nx < 0 || nx >= N || ny < 0 || ny >= N)
							continue;

						if (visit[nx][ny] != 0 || map[nx][ny] == 0)
							continue;

						visit[nx][ny] = apt_comp_count;
						q.push(make_pair(nx, ny));
					}
				}
				house_count_list.push_back(house_count);
			}
		}
	}

	cout << apt_comp_count << '\n';

	sort(house_count_list.begin(), house_count_list.end());
	for (auto i = house_count_list.begin(); i != house_count_list.end(); i++)
		cout << ((*i == 1) ? *i : *i - 1) << '\n';

	return 0;
}

 

음... 꽤 이상한 풀이인 것 같은데 그래도 맞으면 그만이다.