백준 BFS 구현 알고리즘, 16236 아기상어, C++ 문제풀이

 

 

 

 

 

안녕하세요. 오늘은 solved.ac 클래스3 대장문제인 백준 16236번, 아기상어 문제 풀이를 포스팅 해보겠습니다. 제 주언어가 아닌 C++로 오랜만에 풀어본 터라, 코드가 그렇게 깔끔하진 않은 점, 이해 부탁드립니다. 바로 시작하겠습니다.

 

 

 

---

백준 16236, 아기상어 문제 개요

16236번: 아기 상어

백준 16236번, 아기상어 문제는 아기상어가 얼마간의 시간동안 먹이를 찾아서 먹을 수 있는지, 언제까지 엄마상어를 부르지 않고 먹이를 먹을 수 있는지를 찾는 문제입니다. 아기상어가 먹이를 먹는데에 드는 시간은 고려하기 않고, 가장가까운 먹이를, 가장 위쪽(동일한 행에 위치할 경우, 가장 좌측의 먹이)먹이를 우선으로 찾아서 먹게 되며, 자신보다 큰 먹이를 지나갈 수 없는 조건을 잘 적용해서 BFS를 해나가면 문제를 풀 수 있었습니다.

해당문제는 아기상어의 행동 방식 설명을 잘 읽고, 그대로 구현해내면 풀 수 있는 문제였습니다. 문제를 잘읽고 풀어야 하는 문제가 되겠습니다. 문제에 대한 자세한 내용은 위 문제링크를 참고해주세요. 저는 바로 아기상어 C++ 문제풀이 가보겠습니다.

 

 

 

---

백준16236, 아기상어, C++ 문제풀이 설명

먼저, 아기상어와 먹이 등의 정보를 표현하는데 쓸 Pair, PPair 타입을 정의했습니다. dx, dy는 상하좌우 4방향 BFS 구현을 할때 사용합니다. 본 포스팅에서는 이대로 문제를 풀었지만 x, y 좌표변수를 갖는 struct를 구현해서 문제를 푸시면 더 짧고, 깔끔하게 문제를 풀 수 있을 것 같으니 참고하세요.

 

 

 

 

먹이 정보에 대한 구조체, FeedInfo를 구현했습니다. 현재 아기상어의 위치 기준으로 먹이의 위치, 크기, 거리정보를 담을 구조체입니다. idx 변수는 무시해주세요. 구현하고 보니 사용하지 않는 변수입니다. 

 

 

 

 

아기상어 클래스 구현부입니다. 아기상어의 위치, 사이즈, 먹은 먹이의 수 등의 정보를 담고, 먹이탐색, 먹이먹기 함수를 갖고 있습니다. 
68행) eatFeed는 특정 위치의 먹이를 먹고, ,먹은 먹이갯수와 아기상어의 크기를 계산하는 함수입니다.

 

 

 

BShark 클래스의 멤버함수인 searchFeed() 함수는 현재 아기상어 위치를 기준으로 가장 우선순위의 먹잇감을 찾는 함수입니다. 만약 먹을 수 있는 먹잇감이 존재하면 반환하는 pair값의 첫번째 값은 true를, 두번째 값은 먹이의 위치를 반환하도록 했습니다.

65 ~ 83행) 먹이는 BFS 탐색방식으로 찾습니다. 아기상어가 도달할 수 있는 위치들에 한정해서 먹을 수 있는 먹이 리스트를 goodFeedV에 저장합니다.(78행)

85행) 만약 먹을 수 있는 먹이가 없다면, {false, 임의의 쓰레기값}을 반환했습니다.

86 ~ 91행) 가장 가까운 먹이, 만약 가장 가까운 먹이가 다수 존재한다면 가장 위에 있는 먹이, 만약 같은 행의 먹잇감이 있다면, 가장 좌측 먹잇감을 먹을 수 있도록 정렬을 합니다.

정렬이 된 goodFeedV의 첫번째 FeedInfo가 아기상어가 최우선으로 먹어야 하는 먹이정보가 되므로 해당 먹이정보를 pair 결과값으로 반환해줍니다.

 

 

 

 

아기상어 포인터변수 bShark를 선언하고 main() 메인함수 구현을 시작합니다. NxN 크기의 맵의 N 값을 입력받고, 그래프를 표현할 G 이차원 벡터를 선언합니다. 아기상어의 초기 위치정보를 담을 Pair 타입 변수도 선언합니다.

 

 

 

 

전체 먹이갯수를 카운팅할 변수, feedCnt도 하나 선언 후, 그래프정보를 입력받습니다. 아기상어는 9, 빈 칸은 0, 먹이는 1~6으로 표현되므로 이에 맞게 정보를 입력받고 참고해줍니다. 

115 ~ 116행) 아기상어 클래스 객체를 동적할당해주어 사용할 준비르 합니다. time은 아기상어가 먹이를 먹을 수 있는 시간값, 본 문제의 정답결과가 카운팅되어 저장됩니다. 

118행) 더이상 먹을 먹이가 없다면, 이대로 time값을 출력하고 종료합니다.
119 ~ 127행) 아직 먹이가 남아있다면, 아기상어객체의 searchFeed() 함수를 실행해서 먹을 수 있는 먹이가 있으면 먹이를 먹고 feedCnt를 감소시킵니다. 그리고 먹이를 찾아가는데 소요된 시간을 time 변수에 누적시킵니다. 만약, 먹을 수 있는 먹이가 더이상 존재하지 않으면 그대로 현재 time값을 출력합니다.

131행) 아기상어가 먹이를 먹을 수 있는 시간을 출력하고 프로그램을 종료합니다. 

 

---

아래는 제출결과 및 전체소스코드입니다. 매우매우 코드가 정리되어있지 않은점 이해부탁드려요~ 많은 의견과 지적 부탁드립니다. 감사합니다. ^-^//

 

 

 

---

백준 16236, 아기상어 문제 C++ 풀이 제출결과 및 전제 소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N=0;
typedef pair<int, int> Pair;
typedef pair<pair<int, int>, int> PPair;
vector<vector<int>> G;

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

struct FeedInfo {
public:
    Pair pos;
    int size;
    int dist;
    int idx;
    FeedInfo(Pair pos, int size, int dist, int idx) {
        this->pos = pos;
        this->size = size;
        this->dist = dist;
        this->idx = idx;
    }
};

class BShark {
public:
    Pair pos;
    int size;
    int eatCnt;
    BShark(Pair pos, int size) {
        this->pos = pos;
        this->size = size;
        this->eatCnt = 0;
    }
    
    void eatFeed(Pair feedPos) {
        eatCnt++;
        if (eatCnt >= size) {
            eatCnt=0;
            size++;
        }
        G[feedPos.first][feedPos.second] = 0;
        pos = feedPos;
    }
    
    pair<bool, PPair> searchFeed() {
        vector<FeedInfo> goodFeedV;
        queue<PPair> Q;
        Q.push({pos, 0});
        vector<vector<bool>> chkV(N, vector<bool>(N, false));
        chkV[pos.first][pos.second] = true;
        int idx = 0;
        while(!Q.empty()) {
            int x = Q.front().first.first;
            int y = Q.front().first.second;
            int dist = Q.front().second;
            Q.pop();
            for(int i=0; i<4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if(G[nx][ny] > this->size) continue;
                if(chkV[nx][ny]) continue;
                chkV[nx][ny] = true;
                if(G[nx][ny] > 0 && G[nx][ny] != 9 && G[nx][ny] < this->size) {
                    goodFeedV.push_back(FeedInfo({nx, ny}, G[nx][ny], dist+1, idx));
                    idx++;
                }
                Q.push({{nx, ny}, dist+1});
            }
        }

        if ((int)goodFeedV.size() == 0) return {false, {{-1, -1}, 0}};
        sort(goodFeedV.begin(), goodFeedV.end(), [](const FeedInfo &a, const FeedInfo & b) {
            return (a.dist < b.dist) ||
            (a.dist == b.dist && (a.pos.first < b.pos.first
                                  || (a.pos.first == b.pos.first && a.pos.second < b.pos.second)));
        });
        return {true, {goodFeedV[0].pos, goodFeedV[0].dist}};
    }
};

BShark *bShark;

int main() {
    ios_base :: sync_with_stdio(); cin.tie(0);
    cin>>N;
    G = vector<vector<int>>(N, vector<int>(N, 0));
    Pair bsharkPos = {0, 0};
    int feedCnt = 0;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++) {
            cin>>G[i][j];
            if(G[i][j] == 9) {
                bsharkPos = {i, j};
                G[i][j] = 0;
            }
            else if(G[i][j] != 0 && G[i][j] != 9) {
                feedCnt++;
            }
        }
    
    bShark = new BShark(bsharkPos, 2);
    int time=0;
    while (true) {
        if (feedCnt == 0) break;
        G[bShark->pos.first][bShark->pos.second] = 0;
        pair<bool, PPair> searchInfo = bShark->searchFeed();
        if (!searchInfo.first) break;
        else {
            Pair fdPos = searchInfo.second.first;
            int usedTime = searchInfo.second.second;
            time += usedTime;
            bShark->eatFeed(fdPos);
            feedCnt--;
        }
    }

    printf("%d\n", time);
    delete bShark;
}