[문제풀이] 백준 2583 - 영역 구하기

kodaaa·2023년 1월 3일
0

문제풀이

목록 보기
13/23
post-thumbnail

📢 문제

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 수행

  • 📌 2차원 배열로 x,y좌표의 사각형(모눈) 표현하기

  1. [x][y][y][x] 둘다 상관 없음
    다만 2차원 배열의 행, 열을 시각화하면 [y][x]가 그림이 좀더 맞겠지?
  2. x의 좌표가 0~7, y의 좌표가 0~5라고 할 때
    arr[y][x]에서 0<=x<7, 0<=y<5
profile
취뽀하자(●'◡'●)💕

0개의 댓글