백준 16236번 아기 상어

김두현·2022년 12월 6일
백준
1

백준

목록 보기
38/133
post-thumbnail

🔒[문제 url]

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

🔑알고리즘

상어의 이동을 구현하기 전에, 기저 상태로 존재해야하는 것들부터 설정해보도록 하자.

  • 상어가 어떤 정보를 가지고 이동하는가?
    • 우선 상어보다 크기가 작아야하며, 거리가 가까운 물고기부터 먹는다. 거리가 같은 물고기가 많다면 가장 왼쪽 위의 물고기를 택한다.
      따라서, vector에 거리가 같은 경우 왼쪽 위의 물고기부터, 다른 경우 가까운 물고기부터 앞에오도록 정렬한다. 상어가 먹게될 물고기는, 앞에서부터 순회하여 처음으로 만나는 상어보다 작은 물고기이다.
    • 물고기와 상어 모두 크기에 대한 정보를 가지고 있으므로, 각각의 구조체를 선언한다.

  • 물고기의 정렬은 어떻게 진행하는가?
    • 상어와의 거리가 가까운 순서이고, 더 큰 물고기가 있는 칸은 지나갈 수 없으므로 BFS를 이용해 거리를 구한 후 정렬한다. 정렬의 우선순위는 거리 > 위 > 왼쪽이다.

  • 그렇다면 본격적으로 이동을 구현해보자.
  1. 물고기를 정렬한다.
  2. 정렬된 물고기를 순회하며, 크기가 상어보다 작은 물고기를 만나면 거리를 잰다.
  3. 먹을 수 있다면, 거리만큼 시간을 추가한다.
  4. 상어가 있던 자리는 9였으므로 0으로 갱신한다.
  5. 상어의 위치를 먹은 물고기의 자리로 갱신한다.
  6. 상어가 지금까지 먹은 물고기의 수cnt가 상어의 크기와 같아지면 크기를 키운다.
  7. 먹은 물고기의 정보를 지운다.
  8. 상어의 위치가 바뀌었으므로 물고기를 재정렬한다.

    윗 과정을 먹을 수 있는 물고기가 없을 때까지 반복한다.

🐾부분 코드

typedef pair<int, int> pii;
int n;
int map[20][20];

struct Fish
{
    pii pos;
    int size;
};
vector<Fish> fish;

struct Shark
{
    pii pos;
    int size;
    int cnt;
};
Shark shark = { {0,0}, 2, 0 };

int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

<전역 변수 선언>
물고기와 상어는 공통적으로 위치와 크기를 가지고 있으며, 상어는 크기 성장을 위한 cnt 변수또한 선언하여 각각의 구조체를 구현한다.

void INPUT()
{
    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];
            // Push fish info
            if (0 < map[i][j] && map[i][j] < 9)
                fish.push_back({ {i,j},map[i][j] });
            // Note shark's position
            if (map[i][j] == 9) shark.pos = { i,j };
        }
}

<입력 함수>
상어는 9, 물고기는 1 ~ 8이다.

int dist(pii a, pii b)
{// Cannot pass the position that there's a fish bigger than shark
    int visited[20][20]{ 0, };
    queue<pii> q;
    q.push(a);
    visited[a.first][a.second] = 0;

    while (!q.empty())
    {
        pii now = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = now.first + dir[i][0], ny = now.second + dir[i][1];
            if (0 <= nx && nx < n && 0 <= ny && ny < n)
            {
                if (!visited[nx][ny] && map[nx][ny] <= shark.size)
                {
                    visited[nx][ny] = visited[now.first][now.second] + 1;
                    q.push({ nx,ny });
                }
            }
            pii temp = { nx,ny };
            if (temp == b)
            {
                return visited[nx][ny];
            }
        }

    }
    //Cannot go
    return 100;

}

<상어와 물고기 간의 거리 탐색(BFS) 함수>
BFS로 물고기까지의 거리, 즉 먹기까지의 시간을 측정한다.
먹으러 갈 수 없는 경우 100을 return하여 반환 후 예외 처리 해준다.

bool comp(Fish a, Fish b)
{
    int distA = dist(shark.pos, a.pos), distB = dist(shark.pos, b.pos);
    if (distA == distB)
    {
        // if row is same, sort ascending by col
        if (a.pos.first == b.pos.first)
            return b.pos.second > a.pos.second;
        else return b.pos.first > a.pos.first;
    }
    else return distB > distA;
}

<물고기 정렬 기준 설정>
우선순위인 거리 > 위 > 왼쪽을 기준으로 물고기들을 정렬한다.

void SOLVE()
{
    sort(fish.begin(), fish.end(), comp);

    int ans = 0;
    while (true)
    {

        int tempAns = ans;
        for (int i = 0; i < fish.size(); i++)
        {
            if (fish[i].size < shark.size)
            {                
                // Time renewel
                int d = dist(shark.pos, fish[i].pos);
                if (d == 100) break;
                else ans += d;
                // Eat one fish, count it. If cnt == shark's size, Size Up!
                shark.cnt++;
                // shark goes to eat fish[i]
                map[shark.pos.first][shark.pos.second] = 0;
                // shark moved
                shark.pos = fish[i].pos;
                // Fish removed, and now shark's here
                map[fish[i].pos.first][fish[i].pos.second] = 9;

                // Size Up?
                if (shark.cnt == shark.size)
                {
                    shark.size++;
                    shark.cnt = 0;
                }
                // Erase eaten fish's info
                fish.erase(fish.begin() + i);
                // Resort because shark moved
                sort(fish.begin(), fish.end(), comp);
                break;
            }
        }
        if (tempAns == ans)
        {
            cout << ans;
            break;
        }
    }
}

<알고리즘 구현 및 반복>

🪄전체 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> // cpp
#include <stdio.h> // c
#include <string>
#include <memory.h> // memset
#include <algorithm>
#include <cmath>
// 자료 구조
#include <queue>
#include <vector>
using namespace std;

typedef pair<int, int> pii;
int n;
int map[20][20];

struct Fish
{
    pii pos;
    int size;
};
vector<Fish> fish;

struct Shark
{
    pii pos;
    int size;
    int cnt;
};
Shark shark = { {0,0}, 2, 0 };

int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} };

void INPUT()
{
    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];
            // Push fish info
            if (0 < map[i][j] && map[i][j] < 9)
                fish.push_back({ {i,j},map[i][j] });
            // Note shark's position
            if (map[i][j] == 9) shark.pos = { i,j };
        }
}

int dist(pii a, pii b)
{// Cannot pass the position that there's a fish bigger than shark
    int visited[20][20]{ 0, };
    queue<pii> q;
    q.push(a);
    visited[a.first][a.second] = 0;

    while (!q.empty())
    {
        pii now = q.front();
        q.pop();

        for (int i = 0; i < 4; i++)
        {
            int nx = now.first + dir[i][0], ny = now.second + dir[i][1];
            if (0 <= nx && nx < n && 0 <= ny && ny < n)
            {
                if (!visited[nx][ny] && map[nx][ny] <= shark.size)
                {
                    visited[nx][ny] = visited[now.first][now.second] + 1;
                    q.push({ nx,ny });
                }
            }
            pii temp = { nx,ny };
            if (temp == b)
            {
                return visited[nx][ny];
            }
        }

    }
    //Cannot go
    return 100;

}

bool comp(Fish a, Fish b)
{
    int distA = dist(shark.pos, a.pos), distB = dist(shark.pos, b.pos);
    if (distA == distB)
    {
        // if row is same, sort ascending by col
        if (a.pos.first == b.pos.first)
            return b.pos.second > a.pos.second;
        else return b.pos.first > a.pos.first;
    }
    else return distB > distA;
}

void SOLVE()
{
    sort(fish.begin(), fish.end(), comp);

    int ans = 0;
    while (true)
    {

        int tempAns = ans;
        for (int i = 0; i < fish.size(); i++)
        {
            if (fish[i].size < shark.size)
            {                
                // Time renewel
                int d = dist(shark.pos, fish[i].pos);
                if (d == 100) break;
                else ans += d;
                // Eat one fish, count it. If cnt == shark's size, Size Up!
                shark.cnt++;
                // shark goes to eat fish[i]
                map[shark.pos.first][shark.pos.second] = 0;
                // shark moved
                shark.pos = fish[i].pos;
                // Fish removed, and now shark's here
                map[fish[i].pos.first][fish[i].pos.second] = 9;

                // Size Up?
                if (shark.cnt == shark.size)
                {
                    shark.size++;
                    shark.cnt = 0;
                }
                // Erase eaten fish's info
                fish.erase(fish.begin() + i);
                // Resort because shark moved
                sort(fish.begin(), fish.end(), comp);
                break;
            }
        }
        if (tempAns == ans)
        {
            cout << ans;
            break;
        }
    }
}



int main()
{
    INPUT();

    SOLVE();
}

🥇문제 후기

좋아하는 구현 태그에 자신있는 BFS 태그가 곁들여져, 빠르게 풀진 못 했지만 막힘없이 푼 문제. 상어와 물고기를 구조체로 설정하니 게임 만드는 기분이 들어 재미있었다!
근데 코테에서 나왔다고 하면...?😱

💕오류 지적 및 피드백은 언제든 환영입니다. 복제시 출처 남겨주세요!💕
💕좋아요와 댓글은 큰 힘이 됩니다.💕
profile
김두현
I AM WHO I AM
이전 포스트

백준 9019번 DSLR

다음 포스트

백준 13022번 늑대와 올바른 단어

0개의 댓글