https://www.acmicpc.net/problem/2583
BFS/DFS
#include <iostream>
#include <algorithm>
using namespace std;
bool isVisited[101][101]; //방문여부
int M, N, K;
int cnt = 0; //각 영역 크기
void dfs(int x, int y)
{
if (isVisited[x][y])
{
return;
}
isVisited[x][y] = true;
cnt++;
int dx[4] = {0, 0, -1, +1};
int dy[4] = {-1, +1, 0, 0};
for (int i = 0; i < 4; i++)
{
int newX = x + dx[i];
int newY = y + dy[i];
if (0 <= newX && newX < N && 0 <= newY && newY < M && !isVisited[newX][newY])
{
dfs(newX, newY);
}
}
}
int main()
{
cin >> M >> N >> K;
vector<int> result;
//입력받은 부분의 isVisited을 true로
for (int i = 0; i < K; i++)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
for (int x = x1; x < x2; x++)
{
for (int y = y1; y < y2; y++)
{
isVisited[x][y] = true;
}
}
}
// dfs
for (int x = 0; x < N; x++)
{
for (int y = 0; y < M; y++)
{
if (!isVisited[x][y])
{
cnt = 0;
dfs(x, y);
result.push_back(cnt);
}
}
}
cout << result.size() << "\n";
sort(result.begin(), result.end());
for (const auto &e : result)
{
cout << e << " ";
}
}
isVisited
을 false로 초기화할 필요 없음(전역변수라서 자동 초기화됨)
입력받은 사각형들을 이미 방문한 것으로 취급(isVisited
을 true로)한 후,
아무 모눈을 출발점으로 삼아 dfs를 시행 -> 모든 모눈을 방문할 때까지 dfs 수행
[x][y]
나 [y][x]
둘다 상관 없음[y][x]
가 그림이 좀더 맞겠지?arr[y][x]
에서 0<=x<7
, 0<=y<5