[영상처리 스터디] STL queue를 사용해보자.

C++ 환경에서 코딩을 하면 STL이라는 것을 사용할 수 있다.

STL에는 queue가 기본적으로 만들어져있다. 또한 이 queue을 상황에 따라 편하게 선언을 할 수 있다.

STL을 이용하여 n을 입력받고 1부터 n까지의 값을 queue에 넣고 queue에 있던 모든 값을 출력해보는 간단한 소스코드를 작성해보자.

#include<iostream>
#include<queue>
 
using namespace std;
 
queue<int> q;
 
int main()
{
    int n;
    cin >> n; //scanf("%d",&n);
 
    for (int i = 1; i <= n; i++)
    {
        q.push(i);
    }
 
    while (!q.empty())
    {
        cout << q.front() << '\n'; //printf("%d\n",q.front());
        q.pop();
    }
 
    return 0;
}

위 STL queue를 이용해서 단지번호붙이기 문제를 풀기 전에 STL에서 유용하게 쓰이는 것들을 추가로 알려주겠다.

1. pair

pair는 두 가지 자료형을 하나로 묶는데 사용된다. 세 가지 이상을 묶을때에는 구조체가 더 나을 것이다. 하지만 두 가지를 묶어야 하는 상황이 오면 pair가 그나마 편할 것이다.

사용방법은 아주 간단하다. 

#include<pair>
 
using namespace std;
 
pair<int, int> name; //pair 선언
 
name.first = 1;   //페어에 첫번째 값을 1로 대입
name.second = 2;  //페어에 두번째 값을 2로 대입
 
name = make_pair(1,2); //1,2를 하나의 페어로 만들어 대입
//Line 5,6와 Line 8은 똑같은 의미이다.

2. vector

vector는 가변 배열이다. vector를 사용하는 이유는 배열의 크기를 얼만큼 정해야하는지 모를때 사용한다. C에서 동적할당을 이용해서 만들면 되지만 이 vector는 이미 구현되어있는 STL이기 때문에 C++환경에서 코딩을 한다면 이를 이용하는 것이 좋을 때가 있다.

#include<vector>
 
using namespace std;
 
vector<int> name; //vector 선언
 
name.push_back(1); //vector의 맨 뒤에 1 대입
name.push_back(2); //vector의 맨 뒤에 2 대입
 
//벡터 안에 있는 데이터 값
//1 2
 
name.pop_back(); //vector의 맨 뒤의 값을 삭제
 
name[1]; //vector는 배열처럼 원하는 위치를 바로 사용할 수 있다.
 
name.begin() //vector의 맨 앞을 가르키고 있는 포인터
name.end()   //vector의 맨 뒤를 가르키고 있는 포인터
 
 
//더 자세한건 cpp reference에 가서 보면 된다.
//https://en.cppreference.com/w/

3. sort

sort는 아주 좋은 정렬 함수이다. 우리는 아주 간단하게 Bubble sort(버블정렬, 거품정렬), Selection sort(선택 정렬)에 대해 배웠을 텐데, 이에 대한 시간 복잡도는 O(n^2)이다. 기본적으로 선언되어있는 sort의 함수의 시간 복잡도는 O(nlogn)이다.

이때, 시간에 대해 생각하는 방법은 약 1억번의 계산을 할 때 걸리는 시간을 1초라고 생각하면 된다. nlogn과 n^2의 차이는 n와 log n의 차이이다. 아래 그래프를 보면 쉽게 이해가 될 것이다.

sort를 사용하는 방법은 아래와 같다.

#include<vector>
#include<algorithm>
 
using namespace std;
 
vector<int> list;
 
sort(list.begin(), list.end()); //비내림차순으로 정렬
 
//==============================
 
bool compare(int &a, int &b)
{
    return a > b;
}
 
sort(list.begin(), list.end(), compare);
//compare함수의 정의대로 정렬 기준을 정할 수 있음
 

이러한 STL은 검색해보면 자세히 적은 블로그나 Cpp reference를 이용하면 된다. (그래도 모르겠다면 개인적으로 질문해도 괜찮다.)

이제 단지번호붙이기 문제를 풀어보자.

좀 간단히 풀 수 있는 문제지만 영상처리 기법 중 라벨링 기법을 구현 하는 것처럼 짜면 아래와 같다.

#include<iostream> //cstdio
#include<vector>
#include<queue>
#include<algorithm>
 
using namespace std;
 
//pair<int, int> ==> struct pos{int x; int y};
queue<pair<int, int>> q;    //큐 (x,y)
vector<vector<int>> map;    //정보 (2차원 배열)
vector<vector<int>> visit;  //방문 체크(2차원 배열)
vector<int> output;         //결과
 
//위 vector들을 아래와 같이 선언해도 된다.
/*
int map[30][30];
int visit[30][30];
int output[1000]; 
    output배열은 출력 개수를 확실하게 정할 수 없으므로 
    vector를 사용하는게 더 깔끔하고 안전하다.
*/
 
int dx[] = { -1,1,0,0 };
int dy[] = { 0,0,-1,1 };
//4방향을 방문하기 위한 전처리 과정이라고 생각하면 된다.
//
 
int main()
{
    int n;
    scanf("%d", &n);
 
    map.resize(n);
    visit.resize(n);
 
    for (int i = 0; i < n; i++)
    {
        map[i].resize(n);
        visit[i].resize(n);
        for (int j = 0; j < n; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }
 
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (map[i][j] == 1 && visit[i][j] == 0)
            {
                visit[i][j] = 1;
                q.push(make_pair(i, j));
                int area = 0; //
                while (!q.empty())
                {
                    ++area; //넓이 계산
                    pair<int, int> now = q.front();
                    q.pop();
 
                    int ny = now.first;
                    int nx = now.second;
 
                    for (int k = 0; k < 4; k++)
                    {
                        int qy = ny + dy[k];
                        int qx = nx + dx[k];
 
                        if (0 > qy || qy >= n || 0 > qx || qx >= n)continue;
 
                        if (map[qy][qx] == 1 && visit[qy][qx] == 0)
                        {
                            visit[qy][qx] = 1;
                            q.push(make_pair(qy, qx));
                        }
                    }
                }
                output.push_back(area); //구한 넓이를 vector에 대입
            }
        }
    }
 
    printf("%d\n", output.size()); //구한 넓이의 개수가 곧 구역의 개수이다.
 
    sort(output.begin(), output.end()); //넓이를 비내림차순으로 정렬
 
    for (int i = 0; i < output.size(); i++)
    {
        printf("%d\n", output[i]);
    }
 
    return 0;
}