[코딩 스킬] 내 입맛에 맞게 구조체 벡터 정렬하기 + 우선순위 큐

먼저 정렬과 관련한 이전 관련 포스팅을 첨부한다.

1. 문자열 내 입맛대로 정렬하기 (프로그래머스 레벨 2): https://cpp-dev.tistory.com/84

불러오는 중입니다...

2. 우선순위 큐를 이용한 좌표벡터 정렬 활용 (삼성 SW 역테 기출): https://cpp-dev.tistory.com/12?category=852516

불러오는 중입니다...

개인적으로는 우선순위 큐보다 위 1번의 방법대로 새로운 bool 함수를 정의하고 구조체 내부 요소에 원하는 조건대로 bool형을 반환해 사용하는 것이 더욱 편리했다.

 

그런데, 시간 복잡도 상 sort는 O(NlogN)이고, priority_queue는 push/pop시 O(logN)이다.

 

결국 N개의 자료를 먼저 입력받고 sort하나,

N번 자료의 push 또는 pop를 해서 N * O(logN)을 하나 성능은 비슷할 것 같다.

 

이 사항은 위 삼성SW역테 문제 (아기상어)를 우선순위 큐 말고 새 bool 함수 선언을 통한 sort 로 푸는 시도를 해본 뒤, 소요 시간을 비교해 알아봐야 겠다. 이건 오늘중에 문제 풀어보고 포스팅 할 예정이다.

(==> 코드는 바로 아래와 같았고, 실행시간은 priority_queue를 이용해 푼 코드와 동일하게 0ms 소요됐다.)

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
 
using namespace std;
 
struct dir{
    int dr, dc;
};
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
struct shark{
    int r, c, dist;
};
int N;
int answer = 0, size = 2, ate = 0;
vector<vector<int> > map;
vector<vector<bool> > check;
deque<shark> v;
bool cmp(shark a, shark b){
    if (a.dist == b.dist){
        if (a.r == b.r){
            return a.c < b.c;
        }
        return a.r < b.r;
    }
    return a.dist < b.dist;
}
// sort(v.begin(), v.end(), cmp);
void falsing(){
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++)
            check[i][j] = false;
    }
}
 
void bfs(){
    while (!v.empty()){
        // v에는 항상 우선순위가 가장 놓은 것 먼저 오게 되어 있음.
        int dist = v.front().dist;
        int r = v.front().r;
        int c = v.front().c;
        check[r][c] = true;
        v.pop_front();
        if (map[r][c] > 0 && map[r][c] < size){
            map[r][c] = 0;
            ate++;
            if (ate == size){
                ate = 0;
                size++;
            }
            answer += dist;
            dist = 0;
            falsing();
            while (!v.empty()) v.pop_front();
        }
 
        for (int i = 0; i < 4; i++){
            int nr = r + direction[i].dr;
            int nc = c + direction[i].dc;
            if (nr < 0 || nr >= N || nc < 0 || nc >= N) continue;
            if (map[nr][nc] > size) continue;
            if (check[nr][nc]) continue;
            check[nr][nc] = true;
            shark next_s;
            next_s.r = nr, next_s.c = nc, next_s.dist = dist + 1;
            v.push_back(next_s);
            sort(v.begin(), v.end(), cmp);
        }
        //cout << v.size() << '\n';
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    map.assign(N, vector<int>(N, 0));
    check.assign(N, vector<bool>(N, false));
    for (int r = 0; r < N; r++){
        for (int c = 0; c < N; c++){
            cin >> map[r][c];
            if (map[r][c] == 9){
                shark first_pos;
                first_pos.r = r;
                first_pos.c = c;
                first_pos.dist = 0;
                map[r][c] = 0;
                v.push_back(first_pos);
            }
        }
    }
    bfs();
    cout << answer << '\n';
    return 0;
}

 

아무튼!

본론은 sort의 사용자 정의 정렬 방법과 우선순위 큐의 사용자 정의 정렬 방법에 대한 내용이다.

 

처음에는 정말 헤맸다.

왜냐하면 두 놈이 서로 성격이 '반대'이기 때문이었다.

 

본격적으로 시작하기 앞서 참고한 블로그의 링크를 올린다.

상업적 용도도 아니고 뭐 폄훼하는것도 아니니.. 문제가 안되겠지만 문제가 될 시 삭제하겠다.

정리를 잘 해두신 블로그 주인 덕분에 수월하게 이해할 수 있었다.

https://coding-insider.tistory.com/entry/sort-%EC%82%AC%EC%9A%A9%EB%B2%95-priorityqueue%EC%97%90%EC%84%9C%EC%9D%98-sort-%EC%B0%A8%EC%9D%B4

sort 사용법 + priority_queue에서의 sort 방식 차이

1. 정렬 옵션

sort에서 정렬 기준으로 'greater<자료형>()'을 하면 내림차순으로 정렬되지만,

priority_queue에서 정렬 기준으로 'greater<자료형>'을 하면 오름차순으로 정렬된다..

(sort에는 <자료형>뒤에 ()가 붙는것에 유의하자)

1번 까지는 알고 있었다. 그런데.. 

 

2. 정렬 기준

sort는 기준이 왼쪽 요소이지만, priority_queue는 오른쪽 요소가 기준이라는 것이다..

 

충격과 공포 -_-

 

2번을 모르고 계속 남의 코드를 보는데 아무리봐도 이해가 가질 않았다. 이유가 여기에 있었다.

 

새롭게 깨달은 이 통찰로 이전에 짰던 삼성SW역테 아기상어 문제를 아래와 같이 비교해본다.

1. 구 코드

#include <iostream>
#include <queue>
 
using namespace std;
struct dir{
    int dr, dc;
};
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
struct shark{
    int dist, r, c;
    bool operator < (const shark& f) const{ // Min heap 구현
        if (dist == f.dist){
            if (r == f.r) return c > f.c;
            else return r > f.r;
        }
        return dist > f.dist;
    }
};
 
int Map[20][20];
int size = 2, ate = 0, answer=0, N;
bool check[20][20];
priority_queue<shark> pq;
 
void falsing(){
    for (int i = 0; i < 20; i++){
        for (int j = 0; j < 20; j++)
            check[i][j] = false;
    }
}
 
void bfs(){
    while (!pq.empty()){
        // pq top에는 항상 거리>행>열 순으로 상어와 가까운 좌표의 정보가 있음
        int dist = pq.top().dist;
        int row = pq.top().r;
        int col = pq.top().c;
        pq.pop();
        if (Map[row][col] > 0 && Map[row][col] < size){
            // 제일 가까운 곳에서 먹이 발견!
            Map[row][col] = 0;
            ate++;
            if (ate == size){
                size++;
                ate = 0;
            }            
            answer += dist;
            dist = 0;
            falsing();            
            while (!pq.empty()) pq.pop();
            //나머지 비워주자.
        }
 
        for (int i = 0; i < 4; i++){
            int n_r = row + direction[i].dr;
            int n_c = col + direction[i].dc;
            if (n_r < 0 || n_r >= N || n_c < 0 || n_c >= N) continue;
            if (Map[n_r][n_c] > size) continue;
            if (check[n_r][n_c]) continue;
            shark a;
            a.dist = dist + 1;
            a.r = n_r;
            a.c = n_c;
            pq.push(a);
            check[n_r][n_c] = true;
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> Map[i][j];
            if (Map[i][j] == 9){
                shark a;
                a.dist = 0;
                a.r = i;
                a.c = j;
                Map[i][j] = 0;
                check[i][j] = true;
                pq.push(a);
            }
        }
    }
    bfs();
    cout << answer << '\n';
    return 0;
}

 

2. 신코드

#include <iostream>
#include <queue>
 
using namespace std;
struct dir{
    int dr, dc;
};
dir direction[4] = { { 0, 1 }, { 0, -1 }, { 1, 0 }, { -1, 0 } };
 
struct shark{
    int dist, r, c;
};
 
struct cmp{
    bool operator () (shark back, shark front) { // Min heap 구현
        if (back.dist == front.dist){
            if (back.r == front.r) return back.c > front.c;
            else return back.r > front.r;
        }
        return back.dist > front.dist;
    }
};
 
int Map[20][20];
int size = 2, ate = 0, answer = 0, N;
bool check[20][20];
priority_queue<shark, vector<shark>, cmp > pq;
 
void falsing(){
    for (int i = 0; i < 20; i++){
        for (int j = 0; j < 20; j++)
            check[i][j] = false;
    }
}
 
void bfs(){
    while (!pq.empty()){
        // pq top에는 항상 거리>행>열 순으로 상어와 가까운 좌표의 정보가 있음
        int dist = pq.top().dist;
        int row = pq.top().r;
        int col = pq.top().c;
        pq.pop();
        if (Map[row][col] > 0 && Map[row][col] < size){
            // 제일 가까운 곳에서 먹이 발견!
            Map[row][col] = 0;
            ate++;
            if (ate == size){
                size++;
                ate = 0;
            }
            answer += dist;
            dist = 0;
            falsing();
            while (!pq.empty()) pq.pop();
            //나머지 비워주자.
        }
 
        for (int i = 0; i < 4; i++){
            int n_r = row + direction[i].dr;
            int n_c = col + direction[i].dc;
            if (n_r < 0 || n_r >= N || n_c < 0 || n_c >= N) continue;
            if (Map[n_r][n_c] > size) continue;
            if (check[n_r][n_c]) continue;
            shark a;
            a.dist = dist + 1;
            a.r = n_r;
            a.c = n_c;
            pq.push(a);
            check[n_r][n_c] = true;
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> Map[i][j];
            if (Map[i][j] == 9){
                shark a;
                a.dist = 0;
                a.r = i;
                a.c = j;
                Map[i][j] = 0;
                check[i][j] = true;
                pq.push(a);
            }
        }
    }
    bfs();
    cout << answer << '\n';
    return 0;
}

알아보기 쉽게 cmp의 인자를 back, front로 주고 

return에서 front의 인자가 더 작은 것이 오게 하려고 return back.요소 > front.요소 로 하였다.

(문제의 특성상 거리 > 행 > 열 순서로 작은 상어를 앞에 두어야 한다..)

priority_queue는 오른쪽의 요소를 기준으로 동작하기 때문에 이렇게 구현했다.

 

즉, 기준인 오른쪽 front의 요소가 back의 요소보다 작으면 true를 반환하기 때문에 이렇게 return을 하는 것이다.

 

아, 모든 궁금증이 해결됐다.

시원하다.