[백준 16236] 아기 상어 (C++)

문제

백준 16236

16236번: 아기 상어

풀이

문제 풀이 자체는 직관적인데 구현에 시간이 좀 걸렸습니다.

먼저 먹이를 bfs로 찾아줍니다. (먹이는 상어 크기보다 작아야 하고 상어 크기보다 큰 물고기는 지나갈 수 없습니다!!)

먹을 수 있는 먹이가 있으면, 상어가 이동하는 거리를 계산해 dtarr 배열에 넘깁니다.

bfs가 끝나고 먹을 수 있는 먹이가 없으면, 종료하고 cnt를 출력합니다.

먹이가 있다면 가장 짧은 거리, 거리도 같다면 왼쪽 위에 있는 먹이를 목표로 설정합니다.

그 후 먹이가 있던 곳으로 상어를 이동시키고, 원래 상어가 있던 곳은 0으로 바꿔줍니다.

먹이에 따른 상어의 크기 또한 조정합니다.

소스 코드

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
 
int N;
int map[20][20];
int dtarr[20][20];
int xshark, yshark;
int sharksize = 2;
int sharkexp;
bool iseat;
int cnt, dcnt;
bool visited[20][20];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
void bfs(int sx, int sy)
{
    dcnt = 0;
    visited[sy][sx] = true;
    //x좌표, y좌표, 거리
    queue<pair<pair<int, int>, int>> q;
    q.push(make_pair(make_pair(sx, sy), dcnt));
    while (!q.empty())
    {
        int x = q.front().first.first;
        int y = q.front().first.second;
        dcnt = q.front().second;
        //먹이 있으면 거리 계산
        if (map[y][x] < sharksize && map[y][x] != 9 && map[y][x] != 0)
        {
            dtarr[y][x] = dcnt;
            iseat = true;
        }
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < N && ny >= 0 && ny < N)
            {
                if (!visited[ny][nx] && map[ny][nx] <= sharksize)
                {
                    visited[ny][nx] = true;
                    q.push(make_pair(make_pair(nx, ny), dcnt + 1));
                }
            }
        }
    }
    return;
}
 
void fun()
{
    //배열 검색
    while (1)
    {
        iseat = false;
        //먹이 탐색
        bfs(xshark, yshark);
        //먹을 먹이 없으면 종료
        if (!iseat)
        {
            return;
        }
        //먹이 있다면 거리가 가장 짧은 먹이 탐색, 같다면 왼쪽 위에 있는 먹이
        int mindt = 987654321;
        int minx = 0;
        int miny = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (dtarr[i][j] < mindt && dtarr[i][j] != 0)
                {
                    mindt = dtarr[i][j];
                    minx = j;
                    miny = i;
                }
            }
        }
        //이동, 먹이 처리
        cnt += mindt;
        map[yshark][xshark] = 0;
        //상어 이동
        map[miny][minx] = 9;
        xshark = minx;
        yshark = miny;
        //상어 크기 처리
        sharkexp++;
        if (sharkexp >= sharksize)
        {
            sharksize++;
            sharkexp = 0;
        }
        //배열 초기화
        memset(visited, 0, sizeof(visited));
        memset(dtarr, 0, sizeof(dtarr));
    }
}
 
int main()
{
    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)
            {
                xshark = j;
                yshark = i;
            }
        }
    }
    fun();
    cout << cnt;
    return 0;
}