아기상어

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
// 12:15 ~ 1:25
int N,ans;
int board[25][25];
int cost[25][25];
int dx[4] = {0, -1, 1, 0}; // (상 좌 우 하) 우선순위
int dy[4] = {-1, 0, 0, 1};
pair<int,int> shark;
int sharkSize = 2;
int eatFishCnt = 0;
int main() {
    ios::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 >> board[i][j];
            if(board[i][j] == 9)
                shark = {i,j};
        }

    while(true)
    {
        queue<pair<int,int>> q;
        for(int i=0;i<N;i++)
            fill(cost[i], cost[i]+N, -1);
        q.push(shark);
        cost[shark.first][shark.second] = 0;
        pair<int,int> nextDest = {1e9, 1e9};
        while(!q.empty())
        {
            auto cur = q.front(); q.pop();
            for(int dir=0;dir<4;dir++)
            {
                int ny = cur.first + dy[dir];
                int nx = cur.second + dx[dir];
                if(nx<0 or ny<0 or nx>=N or ny>=N) continue;
                if(cost[ny][nx] >= 0 or board[ny][nx] > sharkSize) continue;
                cost[ny][nx] = cost[cur.first][cur.second] + 1;
                /* 빈칸이거나 물고기 크기가 같으면 이동 가능 */
                if(board[ny][nx] == 0 or board[ny][nx] == sharkSize){
                    q.push({ny,nx});
                    continue;
                }else if(board[ny][nx] >=1 and board[ny][nx] <=6){
                    int distCur=1e9;
                    if(nextDest.first != 1e9)
                        distCur = cost[nextDest.first][nextDest.second];
                    int distNext = cost[ny][nx];
                    if(distNext > distCur) continue;
                    else if(distNext < distCur) nextDest = {ny, nx};
                    else if(distNext == distCur){
                        if(ny < nextDest.first)
                            nextDest = {ny,nx};
                        else if(ny == nextDest.first){
                            if(nx < nextDest.second)
                                nextDest = {ny,nx};
                        }
                    }
                }
            }
        }
        if(nextDest.first == 1e9) goto end;
        eatFishCnt++;
        if(eatFishCnt == sharkSize) {
            sharkSize++;
            eatFishCnt = 0;
        }
        board[shark.first][shark.second] = 0;
        board[nextDest.first][nextDest.second] = 9;
        ans += cost[nextDest.first][nextDest.second];
        shark = nextDest;
    }
    end:;
    cout << ans;
    return 0;
}

• 로직
  • shark의 좌표를 시작으로 BFS를 수행해서 가장 가까운 좌표를 찾는다
  • ans를 증가시키고 shark를 update!

• 느낀 것
  : 문제의 조건을 정확하게 파악하지 못해서 시간이 오래걸렸기 때문에 정신을 차려야 한다