알고리즘 스터디

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

2667번: 단지번호붙이기

 

대각선으로는 이동할 수 없고, 상하좌우로만 움직일 수 있기 때문에 axis라는 vector를 만들어서 반복을 돌렸고,

배열을 넘지않도록 조건문 추가

45열과 20열이 같은 조건문이라 줄일수 있는 방법이 있나 생각해봐야 할 것 같다.

 

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

using namespace std;

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

int n;
vector<vector<int>> v(26, vector<int>(26));
vector<vector<bool>> b(26, vector<bool>(26));
vector<int> ans(625);
int c;
string s;
vector<pair<int, int>> axis{ {-1, 0}, {0, 1}, {1, 0}, {0, -1} };	// 왼쪽 위 오른쪽 아래

void dfs(int x, int y) {
	if (v[x][y] == 1 && b[x][y] == false) {
		b[x][y] = true;
		ans[c]++;
		for (auto ai : axis) {
			if (x + ai.first >= 0 && x + ai.first < n && y + ai.second >= 0 && y + ai.second < n) {
				dfs(x + ai.first, y + ai.second);
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> s;
		for (int j = 0; j < s.length(); ++j) {
			v[i][j] = s[j] - '0';
		}
	}
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (v[i][j] == 1 && b[i][j] == false) {
				dfs(i, j);
				c++;
			}	
		}
	}
		
	cout << c << '\n';
	sort(ans.begin(), ans.begin() + c);

	for (int i = 0; i < c; ++i) {
		cout << ans[i] << '\n';
	}

	return 0;
}