https://www.acmicpc.net/problem/2667
문제
> 정사각형 모양의 지도가 있는데 1은 집이있는곳, 0은 집이 없는곳이다.
지도를 이용해 연결된 집의 모임인 단지를 정의하고 단지에 번호를 붙이려 한다.
> 연결되었다는건 상하좌우에 다른집이 있는 경우를 말한다. 대각선상은 아니다.
지도를 입력해 단지수를 출력하고 단지에 속하는 집의 수를 오름차순으로 정렬해 출력해라.접근
사방탐색과 그래프 탐색(DFS, BFS)를 이용해서 집이 있는곳을 탐색해서 수를 누적해 단지의 수와 집의 수를 구한다.
문제해결
> 집의 유무를 나타낼 village를 부울로 선언하고, 사방탐색을 하기 때문에 사방에 대한 방향도 정의해준다.
집을 탐색할 BFS를 정의해주고 집은 좌표로 나타내기 때문에 pair로 입력을 받아준다.
> 입력으로 들어온 첫 집을 통해 house 변수로 해당 집을 잡고 주변집을 탐색한다. 반복문을 통해 사방에대해 탐색하고 만약 village벡터의 값이 1이면(집이존재한다) 그 집들을 큐의 다음에 넣어준다. 그리고 탐색한 집은 부울값을 0으로 바꿔준다.
> 탐색이 끝나면 앞선 탐색에서 봤던 누적된 집의 수를 리턴해준다.
> 입력으로 지도를 받는데 지도에 0과 1로 표시된걸 집 자체의 부울값으로 받아 방문처리도 같이 해버린다.
> 0,0부터 돌며 만약 village가 1인(집이 있다)좌표가 나오면 그 좌표를 BFS에 넣어 결과를 구한다.
그 결과에서 해당 단지의 총 집 수가 나오기 때문에 이를 result벡터에 넣는다.
> 다시 반복을 돌면 단지를 찾는데 앞선 BFS에서 이미 같은 단지에 있는 집은 다 false(village값이 0)으로 바뀌었기 때문에 새로 조건문에 잡히는 좌표는 새로운 단지이다.
> 최종적으로 result 벡터의 크기(단지의 수)와 각 단지의 집 수(각각의 BFS로 리턴된 cnt수)를 출력한다.코드
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;
vector<vector<bool>> village;
int N;
int dx[4] = { 0, 0, -1, 1 };
int dy[4] = { -1, 1, 0, 0 };
int BFS(int r, int c)
{
queue<pair<int, int>> q;
q.push({r, c});
int cnt = 0;
while (!q.empty())
{
pair<int, int> house = q.front();
int fr = house.first;
int fc = house.second;
q.pop();
if (!village[fr][fc])
continue;
village[fr][fc] = false;
cnt++;
for (int i = 0; i < 4; i++)
{
int nr = fr + dx[i];
int nc = fc + dy[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= N)
continue;
if (village[nr][nc])
{
q.push({ nr, nc });
}
}
}
return cnt;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N;
village.assign(N, vector<bool>(N));
for (int i = 0; i < N; i++)
{
string str;
cin >> str;
for (int j = 0; j < N; j++)
{
village[i][j] = str[j] - '0'; //집없는데가 false 있는데가 true
}
}
vector<int> result;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (village[i][j]) result.push_back(BFS(i, j));
}
}
sort(result.begin(), result.end());
cout << result.size() << '\n';
for (auto a : result)
cout << a << '\n';
}
후기
사방탐색에 대한 문제가 두번째라 익숙하지 않아 좀 헤맸다.
그래도 입력으로 들어온 0과 1로 바로 집에 대한처리, 방문처리까지 해버려서 훨씬 간단하고 짧게 해결한것 같다. 좀 늘은것 같다.
