백준 2583번 영역 구하기

 

 

문제 보러가기 : https://www.acmicpc.net/problem/2583

 

 

2583번: 영역 구하기

 

 

이번 문제는 그래프 탐색 문제였습니다. (본인은 DFS 알고리즘으로 풀었습니다.)

 

 

💡 My Case 💡

모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 모눈종이를 뒤집어도 영역의 넓이는 그대로이므로 왼쪽 아래 꼭짓점의 좌표와 오른쪽 위 꼭짓점의 좌표로 값을 채워넣어도 되지만, 본인은 문제에 그려진 위치에 직사각형을 그렸습니다.

 

 

 

《문제 풀이》

 

1. 모눈종이 위에 K개의 직사각형을 그리기 위해 해당 좌표를 -1 값으로 채움 (drawRectangle 함수)

2. graph_paper[i][j] == 0 이고 해당 눈금을 방문하지 않았다면 영역의 넓이를 구함 → 이 때, cnt 변수를 0으로 초기화

3. getArea() 수행

     (1) 현재 눈금의 상하좌우 눈금 각각에 대해 범위를 검사 (범위를 벗어나지 않으면 (2) 진행)

     (2) 해당 눈금의 값이 0이고 아직 방문하지 않은 눈금이라면 getArea(nx, ny)

     (3) getArea() 가 호출되면 영역의 넓이 1 증가 (cnt++)

4. cnt 를 벡터에 삽입

 

 

 

《C++ 코드》

 

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 100

using namespace std;

int m, n, k, cnt;
int left_x, left_y, right_x, right_y;
int graph_paper[MAX][MAX];
bool visited[MAX][MAX];

typedef struct {
  int x, y;
}box;

box moveD[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

// 직사각형을 그리는 함수 
void drawRectangle(int lx, int ly, int rx, int ry) {
  for (int i=m-ry; i<=m-ly-1; i++) {
    for (int j=lx; j<=rx-1; j++) {
      if (graph_paper[i][j] == -1) continue;
      graph_paper[i][j] = -1;
    }
  }
}

// 각 영역의 넓이를 구하는 함수 
void getArea(int x, int y) { 
  visited[x][y] = true;
  cnt++;

  for (int i=0; i<4; i++) {
    int nx = x + moveD[i].x; 
    int ny = y + moveD[i].y; 

    if (nx < 0 || m <= nx || ny < 0 || n <= ny) continue; // 범위를 벗어나면
    if (graph_paper[nx][ny] == -1 || visited[nx][ny]) continue; // 직사각형이 그려져 있거나 이미 방문했다면
    getArea(nx, ny); 
  }
}

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

  cin>>m>>n>>k;
  for(int i=0; i<k; i++) {
    cin>>left_x>>left_y>>right_x>>right_y;
    drawRectangle(left_x, left_y, right_x, right_y);
  }

  vector<int> area; // 각 영역의 넓이를 담을 벡터

  for (int i=0; i<m; i++) {
    for (int j=0; j<n; j++) {
      if (graph_paper[i][j] == 0 && !visited[i][j]) {
        cnt = 0; // 각 영역의 개수를 세기 위한 변수
        getArea(i, j);
        area.push_back(cnt); 
      }
    }
  }
  sort(area.begin(), area.end());
  
  cout<<area.size()<<"\n";
  for (int i=0; i<area.size(); i++) 
    cout<<area[i]<<" ";
  
  return 0;
}

 

 

개발 환경: Visual Studio Code

 

 

Baekjoon - 정답 화면