[삼성SW테스트] 백준 16236번 - 아기 상어(w/ 우선순위 큐)

삼성 소트프웨어 역량테스트 기출문제다.

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

16236번: 아기 상어

BFS 문제로 조건에 맞는 탐색문제유형이다.

주어진 조건이 세 개 정도 되는데 그것은

1. 상어는 빈 공간(0)이나 자기보다 크기가 작거나 같은 물고기가 있는 공간으로 갈 수 있다.(상하좌우)

   이 때, 크기가 작은 물고기를 만나면 상어가 물고기를 잡아먹고, 잡아먹은 물고기 수가 자신의 크기와 동일하면 잡아먹은 물고기의 수를 0으로 하고 자신의 크기를 +1한다. 만약 자신과 동일한 크기의 물고기를 만나면 해당 물고기의 위치로 이동을 할 수는 있지만 잡아먹지는 못한다. (즉 빈 공간과 같이 경로로 이동만 가능하다.)

2. 물고기를 먹으러 이동하는 조건은 가장 가까우면서 좌상단에 있는 물고기를 우선으로 먹는다는 것이다.

3. 물고기를 다 먹어 더이상 먹을 수 있는 물고기가 없을 경우 이동에 소요된 총 시간을 출력한다.

 

초기에는 vector<int, pair<int, int> > v에 물고기들의 크기와 위치 정보를 pair로 넣고, 현재 상어의 위치에서 주어진 조건에 맞게 bfs를 하나하나 물고기에 적용해 장애물을 피해 이동에 필요한 총 거리를 먼저 계산하고, 이를 다시 거리와 해당 물고기의 좌표를 vector<int, pair<int, int> > 화 하고 <algorithm>의 sort 함수를 사용해 구현하였으나 너무 복잡하고 코드가 길어졌다.

 

그래서 다른 방법은 없을까하고 다른 코드들을 살펴본 결과, '우선순위 큐'를 활용해 이 문제를 푼 사람들이 다수있다는걸 알게되었다. <algorithm>의 소트나 next_permutation 함수, <functional>의 grater<자료형>() 인자, <vector>, <queue>, <deque>, <map>, <set> 자료구조를 사용해본 적은 있지만, <queue>의 priority_queue는 처음 사용해보아 관련된 STL 문서들을 보며 예제로 새로 사용법을 익혔다.

관련된 해외 커뮤니티 사이트 - https://discuss.codechef.com/t/how-to-use-the-priority-queue-stl-for-objects/3514/1

How to use the priority queue STL for objects?

이 우선순위 큐의 장점은 이 문제와 같이 동일한 거리라는 우선순위 다음으로 어떤 우선순위로 후보를 결정해야하는 경우가 생길 경우, 간단하게 STL의 자료구조에서 알아서 소팅해서 top()에 가장 좋은 후보를 가져다 놓는다는 것이었다. 이 문제에서는 거리순, 행순, 열순으로 물고기를 먹으러 가야한다는 조건을 제시했는데, 이런 조건에 대해 가장 쉽게 코딩을 할 수 있도록 도와주는 게 이 우선순위 큐임을 깨닫게 되었다. 그리고, 일반 queue와 다르게 front()로 인자를 가져오는게 아니라 top()으로 가장 우선순위 높은 원소를 가져올 수 있고, empty()로 비어있는지 유무를 확인할 수 있으며, push(), pop()으로 원소를 넣고 뺄 수 있다.

 

단, 이 문제에서 유의할 점은 우선순위가 

1. 거리가 짧은 물고기

2. 1번 조건의 물고기가 많다면 더 위에 있는 물고기(행 인덱스가 더 작은)

3. 2번 조건의 물고기가 많다면 더 왼쪽에 있는 물고기(열 인덱스가 더 작은)

로 적용되어야 하기 때문에, 디폴트로 Max heap을 사용하는 priority_queue의 비교 연산자 오버로딩이 필요했다는 것이었다. (상세 예시는 위 두번째 링크 참조.)

 

또한, 우선순위가 가장 높은 물고기를 찾아 먹고나서 크기 변환 및 먹은 물고기 수 초기화 작업, 방문 여부의 재 초기화 정도를 신경쓰는 꼼꼼함이 필요했다.

 

아래는 전체 C++ 코드이다.

 

#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;
}

 

기존 코드보다 1/2길이에 더욱 직관적인 코드가 완성되었다.

앞으로 비슷한 유형이 나오면 적극 priority_queue를 사용해야겠다.

 

이것저것 해본 코드도 첨부한다.

 

#include <iostream>
#include <queue>
#include <functional>
 
using namespace std;
struct user_defined{
    int a;
    bool operator < (const user_defined& b) const{
        if (a <= b.a) return a > b.a;
    }
};
int main(){
    priority_queue<user_defined> pq;
    user_defined u_d;
    u_d.a = 7;
    pq.push(u_d);
    u_d.a = 3;
    pq.push(u_d);
    u_d.a = 1;
    pq.push(u_d);
    u_d.a = 1;
    pq.push(u_d);
    int loop_cnt = pq.size();
    for (int i = 0; i < loop_cnt; i++){
        cout << pq.top().a << '\n';
        pq.pop();    
    }
    // 1. 사용자 정의 자료형을 작은 원소부터 넣도록 설정
    // 출력: 1 1 3 7
 
    cout << '\n' << '\n';
    priority_queue<int, vector<int>, less<int> > pq2;
    pq2.push(3);
    pq2.push(7);
    pq2.push(1);
    int loop_cnt2 = pq2.size();
    for (int i = 0; i < loop_cnt2; i++){
        cout << pq2.top() << '\n';
        pq2.pop();
    }
    // 2. queue로 큰 원소부터 넣도록 설정
    // 출력: 7 3 1
 
    cout << '\n' << '\n';
    priority_queue<int, deque<int>, greater<int> > pq3;
    pq3.push(3);
    pq3.push(7);
    pq3.push(1);
    int loop_cnt3 = pq3.size();
    for (int i = 0; i < loop_cnt3; i++){
        cout << pq3.top() << '\n';
        pq3.pop();
    }
    // 3. deque로 작은 원소부터 넣도록 설정
    // 출력: 1 3 7
    return 0;
}

 

추가) <algorithm>의 sort에 보면 인자로 정렬 옵션을 줄 수 있는데, int 형의 경우 <functional> 라이브러리의 greater<int>()을 주면 내림차순으로 정렬할 수 있다. 즉, 앞에 가장 큰 요소가 오는 것이다.

 

하지만 라이브러리 <functional>을 추가하고, priority_queue에서 자료형을 int로 쓰는 자료구조 queue로 구현한다고 가정했을 때,

 

priority_queue<int, vector<int>, greater<int> > pq; 를 선언하면

pq.push(7);

pq.push(6);

pq.push(3);

pq.push(100);

을 하고 pq의 요소들을 출력하면 3, 6, 7, 100의 순으로 저장되어있는 것을 알 수 있다. 즉, 우선순위 큐에서 옵션으로 greater가 주어지면 작은 원소부터 저장해 큰 원소가 저장되도록 설정된다는 것을 알 수 있다. (디폴트로 우선순위 큐는 벡터로 구현돼있다. deque도 쓸 수 있다. queue는 x.)

 

sort 함수는 옵션이 greater이면 큰것부터 내림차순으로,

우선순위큐의 옵션이 greater이면 작은것부터 큰것으로 저장된다!