#2583 영역 구하기

https://www.acmicpc.net/problem/2583

2583번: 영역 구하기

실버 1의 문제이다. 이정도 문제는 골드 5는 줘도 되지 않을까 하는 생각도 들지만 뭐...풀었으니 됐다.

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

int m,n,k;
int map[101][101];
int visited[101][101];
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
vector<int> area;
int cnt,AREA;
queue<pair<int,int>> q;

void bfs(int x,int y){
  q.push(make_pair(x,y));
  visited[x][y]=1;
  AREA=0;
  while(!q.empty()){
    x=q.front().first;
    y=q.front().second;
    q.pop();
    for(int z=0;z<4;z++){
      int nx=x+dx[z];
      int ny=y+dy[z];
      if(0<=nx && nx<m && 0<=ny && ny<n){
        if(map[nx][ny]==0 && visited[nx][ny]==0){
          q.push(make_pair(nx,ny));
          visited[nx][ny]=1;
          AREA++;
        }
      }
    }
  }
  area.push_back(AREA);
}

int main()
{
  //freopen("input.txt","r",stdin);
  cin>>m>>n>>k;
  int coord[k][4];
  for(int i=0;i<k;i++){
    for(int j=0;j<4;j++){
      cin>>coord[i][j];
    }
  }

  for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
      for(int x=0;x<k;x++){
        if(m-coord[x][1]>i && i>=m-coord[x][3] && coord[x][0]<=j && j<coord[x][2])
          map[i][j]=1;
      }
    }
  }

  for(int i=0;i<m;i++){
    for(int j=0;j<n;j++){
      if(map[i][j]==0 && visited[i][j]==0){
        bfs(i,j);
        cnt++;
      }
    }
  }

  for(int i=0;i<area.size();i++)
    area[i]+=1;

  sort(area.begin(),area.end());
  cout<<cnt<<'\n';
  for(int i=0;i<area.size();i++)
    cout<<area[i]<<" ";
}

코드가 좀 길다. 문제에서 원하는게 많아가지고 좀 길어진 것 같다. 이 문제의 핵심은 행,열 을 어떻게 해야 우리가 흔히 수학에서 쓰는 좌표계로 바꿀 수 있을까이다.

코딩에서 쓰이는 행,열 과 수학에서의 좌표는 같은것이 있다. 그것은 y축이다. 행렬에서의 열과 좌표에서 y축은 같은 것을 나타낸다. 유일하게 다른점은 x축과 행 인데, 이는 쉽게 바꿀 수 있다. 입력받은 행의 크기 - 원하는 행의 값 = 원하는 x좌표값 이 된다. 이를 토대로 입력받은 coord배열, 즉 행렬을 x,y 축으로 바꿈과 동시에 문제에서 영역을 칠하기 위해서 1을 대입해 주었다. map배열에서 1이 있는 것은 칠해진 영역을 의미한다.

 

이 과정 이후로는 쉽다. 여태 하던 것 처럼 bfs를 돌려 영역의 개수를 찾아주고 이를 출력해준다. 또한 각 영역의 크기를 구하기 위해서 area 벡터를 선언해서 여기에 각 영역의 넓이를 넣어주었다. 문제에서 영역의 넓이를 오름차순으로 출력하라 했으니 sort함수를 사용해서 정렬 해준 다음 그대로 출력했다.

 

어렵지는 않았는데 행렬<->좌표 의 과정과, 원하는 것이 좀 많아서 오래걸렸다 ㅎㅎ;;