[C++] BOJ 2583 / BFS (sort 사용)

문제 분석

기본 BFS 문제와 기본 틀은 같다. 영역의 크기와 분리된 영역의 개수를 BFS 를 통해서 구하면 된다.

 

해결 방법

칠한 부분을 "벽"이라고 가정한 후 나머지 영역에서 BFS를 적용하면 된다.

주어지는 좌표 값이 왼쪽 모서리의 좌표와 오른쪽 모서리의 좌표가 주어지는데, 이를 2차원 배열에 행 열로 넣으면 그림이 거꾸로 나온다. 하지만 영역의 크기를 계산하면 되는 문제이기 때문에 상관없다.

영역의 크기를 "오름차순"으로 정렬하여 출력하라는 조건이 주어졌기 때문에 Sort 함수를 사용하였다.

 

코드

#include <iostream>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>

using namespace std;
#define X first
#define Y second
int board[101][101];
int vis[101][101];
int dx[4]={1,0,-1,0};
int dy[4]={0,-1,0,1};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,m,k;
    int lx,ly,rx,ry;
    int area=0, sum=0;
    vector<int> vec;
    queue<pair<int,int>> q;
    cin >> n >> m >> k;
    while(k--) {
        cin >> lx >> ly >> rx >> ry;
        for(int i = ly ; i < ry ; i++) {
            for(int j = lx ; j < rx ; j++) {
                board[i][j] = -1;
            }
        }
    }
    for(int i=0;i<n;i++) {
        for(int j=0;j<m;j++) {
            if(board[i][j] == -1 || vis[i][j] == 1) continue;
            q.push({i,j});
            vis[i][j] = 1;
            area++;
            while(!q.empty()) {
                pair<int,int> cur = q.front();
                q.pop();
                sum++;
                for(int dir=0;dir<4;dir++) {
                    int nx = cur.X + dx[dir];
                    int ny = cur.Y + dy[dir];
                    if(nx<0||nx>=n||ny<0||ny>=m) continue;
                    if(vis[nx][ny] == 1 || board[nx][ny] == -1) continue;
                    q.push({nx,ny});
                    vis[nx][ny] = 1;
                }
            }
            vec.push_back(sum);
            sum=0;
        }
    }
    sort(vec.begin(), vec.end());
    cout << area << "\n";
    for(auto e : vec)
        cout << e << " ";

}

 

- sort

필요한 헤더파일은 <algorithm> 이다.

vector<int> vec;
sort(vec.begin(), vec.end());

첫 번째 인자로는 정렬하고자 하는 리스트의 시작점이, 두 번째 인자로는 리스트의 끝점이 들어간다.

세 번째 인자는 Compare 방식이 들어가야 한다. 위의 코드에서는 세 번째 인자가 생략되어 있는데, 이는 선택사항이며 기본 값은 "오름차순" 이다.

 

bool compare(int i, int j) {
	return j < i;
}
sort(vec.begin(), vec.end(), compare);

"내림차순"으로 정렬하고자 한다면, 직접 compare 함수를 구현하여 인자로 넘겨주면 된다.

이보다 더 간편하게 구현하는 방식은 아래와 같이 greater<>() 임시객체를 콜 하는 방식이다.

sort(vec.begin(), vec.end(), greater<>())

 

참고 링크

• Sort 함수
  • https://itguava.tistory.com/67