[2583] 영역 구하기(C++)

문제

2583번: 영역 구하기

 

 

해결 방법

저번주에 도전하다가 결국 실패해서 과제로 제출하지 못한 문제이다.

연휴라 시간도 많고 이걸 해결하지 못하면 다른 bfs문제도 풀 수 없을 것 같아서 다시 도전하기로 했다.

 

내가 생각하는 좌표의 시작점과, 컴퓨터가 입력받는 좌표의 시작점과 다른 것을 주의해서 보면 됐던 문제.

초기화 상태

컴퓨터가 인식한 초기화 상태

내가 원하는 좌표평면은 원점이 왼쪽아래지만 컴퓨터 상에서 원점은 왼쪽상단이기 때문에

이걸 바꿔주는 작업이 필요하다.

 

내가 입력한 상태

컴퓨터가 입력받은 상태

예를 들어 x1, y1, x2, y2를 각각 0, 2, 4, 4로 입력받았다면,

컴퓨터 상의 좌표평면에서 2행 3 ~ 0열, 1행 3 ~ 0열 이렇게 순환하도록 만들 것이다.

 

그래서!

행은 (m - 1 - y1)부터 시작해서 (y2 - y1)만큼 순환하면 되므로 (m - 1 - y1) - (y2 - y1 - 1) = (m - y2)까지 돌면 되고,

열은 내가 입력한 상태나 컴퓨터가 입력받은 상태나 똑같기 때문에 x2 - 1부터 x1까지 순환하게 만들면 된다.

 

 

내 코드(C++)

/*[2583] 영역구하기*/
/*https://www.acmicpc.net/problem/2583*/
/*BFS*/

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

int m, n; //height, width
int cnt = 0; //the number of connected components
int maze[101][101] = { 0, };
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0, -1 };
vector<int>area;
void bfs(int x, int y);

int main(void)
{
    int k; //the number of squares
    int x1, x2, y1, y2;
    cin >> m >> n >> k;
    
    for (int i = 0; i < k; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        
        //row
        for (int j = m - 1 - y1; j >= m - y2; j--) {
        	//column
            for (int k = x2 - 1; k >= x1; k--) {
                if(maze[j][k]==0) //empty
                    maze[j][k] = 1;
            }
        }
    }
    
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
        	//empty
            if (maze[i][j] == 0) 
                bfs(i, j);
        }
    }
    
    cout << cnt << endl;
    sort(area.begin(), area.end());
    
    for (int i = 0; i < area.size(); i++) {
        cout << area[i] << " ";
    }
    
    return 0;
}

void bfs(int x, int y)
{
    int sum = 0; //area of connected component
    queue<pair<int, int> >q;
    q.push(make_pair(x, y));
    maze[x][y] = 2; //visited

    while (!q.empty()) {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        sum++;
        
        //east, north, west, south
        for (int i = 0; i < 4; i++) {
            int nextx = x + dx[i];
            int nexty = y + dy[i];

            if (0 <= nextx && nextx < m && 0 <= nexty && nexty < n && maze[nextx][nexty] == 0) {
                maze[nextx][nexty] = 2;
                q.push(make_pair(nextx, nexty));
            }
        }
    }
    
    area.push_back(sum);
    cnt++; //bfs end
}