[현대 소프티어] (C++) 장애물 인식 프로그램

완전탐색 문제이다.

DFS로 풀었으며 map의 count를 매개변수로 주었다가 틀렸었다.

매개변수로 줄 필요없이 DFS 함수의 실행 숫자를 세면 그 영역의 넓이가 나온다.

그 외에는 자주 풀던 문제라 어려움 없이 풀 수 있었다.

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

using namespace std;

#define MAX 26

int N;
vector<string> map;
bool visited[MAX][MAX] = { 0 };
vector<int> ans;
int map_cnt = 0;

int ROTATE_X[] = { -1, 0, 0, 1 };
int ROTATE_Y[] = { 0, -1, 1, 0 };

void DFS(int x, int y) {

	visited[x][y] = true;

	map_cnt++;

	for (int i = 0; i < 4; i++) {
		int next_x = x + ROTATE_X[i];
		int next_y = y + ROTATE_Y[i];

		if (next_x < 0 || next_x >= N || next_y < 0 || next_y >= N)
			continue;

		if (!visited[next_x][next_y] && map[next_x][next_y] == '1')
			DFS(next_x, next_y);
	}
}

int main(int argc, char** argv)
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N;

	string a;
	for (int i = 0; i < N; i++) {
		cin >> a;
		map.push_back(a);
	}

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

	sort(ans.begin(), ans.end());

	cout << ans.size() << '\n';
	for (int i = 0; i < ans.size(); i++)
		cout << ans[i] << '\n';

	return 0;
}