[Algorithm] 백준 16236번 아기 상어

아기상어 뚜루루뚜루 귀여운 뚜루루뚜루

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

오늘도 매우 분노에 가득한 채 완료.

학습 내용

1. Custom object에 대한 vector sorting 방안

- 아래 source code 내 15 ~ 30 Line에서 custom object에 대한 comparator 구현

- 이번 문제에 맞게 여러 후보들((x,y)를 가지는 point 임) 중에서 가장 위에 있고 (x가 작은) 가장 왼쪽에 있는 (y가 작은) 순서대로 sorting 할 수 있도록 구현하였음.

2. Struct 구조체 사용 및 적응

- C++ 에서 생성자를 생성해봤음.

- PointCustom() : x(0), y(0) {}   →→→→  PointCustom이 parameter 없이 생성될 때 각 초기화 값을 설정함.

- PointCustom(int x, int y) : x(x), y(y) {}  →→→→  PointCustom이 parameter를 기반으로 생성될 때 각 값을 해당 param으로 설정함.

3. 오늘 기억을 되살린 팁

- int 변수가 0이면, if 조건에서 false의 역할을 함. (ex if(temp)   temp가 0이면, false로 if를 통과하지 않음)

문제 이해

1. 아기 상어의 초기 크기는 2이다.

2. 아기 상어의 가능한 이동 경로

- 아기 상어와 같거나 작은 먹이만 통과할 수 있음.

- 아기 상어보다 큰 먹이는 통과할 수 없음.

3. 아기 상어가 먹을 수 있는 먹이

- 아기 상어보다 작은 크기의 먹이는 먹을 수 있음.

- 아기 상어와 같은 크기의 먹이는 먹을 수 없음.

- 아기 상어보다 큰 크기의 먹이는 먹을 수 없음. (애초에 지나갈 수 없음)

4. 아기 상어가 먹이를 먹는 조건  ( 해당 조건은 위의 학습 내용에서 vector sorting 관련하여 언급함 )

- 크기와 무관하게 가장 가까운 거리에 있는 먹이를 먹는다.

- 같은 거리에 여러 개의 먹이가 있다면, 가장 위에 있는 먹이를 먹는다.

- 같은 거리에 있고, 가장 위에 있는 먹이가 여러 개라면 그 중에서 가장 왼쪽에 있는 먹이를 먹는다.

5. 아기 상어의 크기가 커지기 위한 조건

- 현재 크기가 2 라고 가정하면, 2개의 먹이를 먹어야 크기가 1 커짐.

- 현재 크기가 N 이라고 가정하면, N개의 먹이를 먹어야 크기가 1 커짐.

문제 해결 방법

1. 아기 상어가 "위의 문제 이해 - 아기 상어가 먹을 수 있는 먹이"를 찾는다. 

2. 아기 상어가 먹을 수 있는 먹이에 이동할 수 있는 지 "위의 문제 이해 - 아기 상어의 가능한 이동 경로"를 확인한다.

3. 아기 상어가 "위의 문제 이해 - 아기 상어가 먹이를 먹는 조건"에 맞는 먹이를 먹는다.

4. 아기 상어가 먹이를 먹은 후, "위의 문제 이해 - 아기 상어의 크기가 커지기 위한 조건"에 맞는 성장 가능성을 확인한다. 

아기 상어가 엄마에게 헬프를 쳐야하는 케이스(=문제 종료)

1. 아기 상어보다 큰 먹이만 남아있을 때 (아래의 source code에서는 pointsCount vector를 통해 확인함)

2. 맵에 먹이가 하나도 남지 않았을 때 (아래의 source code에서는 eatNumber로 확인함)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
using namespace std;
 
struct PointCustom {
    int x;
    int y;
    PointCustom() : x(0), y(0) {}
    PointCustom(int x, int y) : x(x), y(y) {}
};
// true : 먹이가 a, false : 먹이가 b
bool compPointCustom(const pair < PointCustom, int > &a, const pair < PointCustom, int > &b) {
    if (a.first.x < b.first.x) {
        return true;
    }
    else if (a.first.x == b.first.x) {
        if (a.first.y < b.first.y) {
            return true;
        }
        else {
            return false;
        }
    }
    else {
        return false;
    }
}
int N;
vector < vector <int> > map;
vector < vector < PointCustom > > points;
vector < int > pointsCount;
pair < PointCustom, int > baby;
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
int eatNumber;
int main()
{
    cin >> N;
    map.assign(N + 1, vector<int>(N + 1, 0));
    points.assign(7, vector<PointCustom>());
    pointsCount.assign(7, 0);
    PointCustom temp = PointCustom(0, 0);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
            if (map[i][j] == 9) {
                baby = make_pair(PointCustom(i, j), 2);
                map[i][j] = 0;
            }
            else if (map[i][j] != 9 && map[i][j] != 0) {
                points[map[i][j]].push_back(PointCustom(i, j));
                pointsCount[map[i][j]]++;
                eatNumber++;
            }
        }
    }
 
    int answer = 0;
    bool isFinish = false;
    int eatCount = 0;
    // int=0 false 그외는 true
    while (!isFinish && eatNumber) {
        queue < pair < PointCustom, int > > q;
        q.push(make_pair(baby.first, 0));
        vector < pair < PointCustom, int > > eatableQ;
        bool isSubFinish = false;
 
        vector < vector <int> > visit;
        visit.assign(N + 1, vector<int>(N + 1, 500));
 
        int eatQcnt = 0;
        while (!q.empty() && eatNumber) {
            bool isForceExit = true;
            for (int i = 1; i < baby.second; i++) {
                if (i > 6) break;
                if (pointsCount[i] != 0) isForceExit = false;
            }
            if (isForceExit) break;
 
            PointCustom curPoint = q.front().first;
            int tempCount = q.front().second;
            q.pop();
 
            if (tempCount + 1 != eatQcnt && !eatableQ.empty()) {
                eatNumber--;
                eatCount++;
                sort(eatableQ.begin(), eatableQ.end(), compPointCustom);
                PointCustom temp = eatableQ.front().first;
                pointsCount[map[temp.x][temp.y]] --;
                map[temp.x][temp.y] = 0;
                if (eatCount == baby.second) {
                    baby.second += 1;
                    eatCount = 0;
                }
                baby.first = temp;
                answer += eatableQ.front().second;
                isSubFinish = true;
                eatableQ.clear();
                break;
            }
 
            int cx, cy;
            for (int i = 0; i < 4; i++) {
                cx = curPoint.x + dx[i];
                cy = curPoint.y + dy[i];
                if (cx >= 0 && cy >= 0 && cx < N && cy < N) {
                    if (visit[cx][cy] <= tempCount + 1) continue;
                    if (map[cx][cy] == baby.second || map[cx][cy] == 0) {
                        q.push(make_pair(PointCustom(cx, cy), tempCount + 1));
                        visit[cx][cy] = tempCount + 1;
                    }
                    else if (map[cx][cy] < baby.second) {
                        eatableQ.push_back(make_pair(PointCustom(cx, cy), tempCount + 1));
                        eatQcnt = tempCount + 1;
                        visit[cx][cy] = tempCount + 1;
                    }
                }
            }
        }
        if (!eatableQ.empty()) {
            eatNumber--;
            eatCount++;
            sort(eatableQ.begin(), eatableQ.end(), compPointCustom);
            PointCustom temp = eatableQ.front().first;
            pointsCount[map[temp.x][temp.y]] --;
            map[temp.x][temp.y] = 0;
            if (eatCount == baby.second) {
                baby.second += 1;
                eatCount = 0;
            }
            baby.first = temp;
            answer += eatableQ.front().second;
            isSubFinish = true;
        }
        if (!isSubFinish) {
            isFinish = true;
        }
    }
    cout << answer;
    system("pause");
    return 0;
}

ㅇ

원래부터 못했는데 여태 운이 좋았던 건지, 원래는 잘했으나 지금은 못하는 건지 어떤 상황이든지 열심히 해야징

빠이루 도움이 됐길 바랍니다~~ !~~~~~~