[C++] 백준 #16236 아기상어

문제

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

16236번: 아기 상어

시간초과 코드

처음엔 재귀함수로 풀었다.

입력받을 때 아기상어의 위치를 저장하고

1. 각 칸을 탐색하며, 자신의 몸집보다 작은 물고기를 찾는다.
   1. 찾았을 경우 상어의 위치에서 해당 물고기까지의 거리를 계산하는데 (최단 경로이기 위해), 이 때 재귀함수를 썼다.
   2. 한마리라도 찾았을 경우에는 check=true 를 만들어준다.
      1. 최종적으로 최단경로를 저장한 후에는 상어가 그 쪽으로 이동해 물고기를 먹게끔 구현했다.
      2. 이 때, 마지막 물고기인데 자기 몸집보다 크거나 같을 경우를 대비해 boolean 변수를 하나 더 만들었다.

하지만 ide로 돌릴 때도 결과가 바로바로 나오지 않았고, 결국 시간초과가 떴다.

//
// Created by ღ 𝚂𝚑𝚒𝚗𝚎 𝚈𝚎𝚘𝚗 ღ on 2022/10/11.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

int N;
int board[21][21];
bool visited[21][21];
int sharkX, sharkY; //아기상어 위치 저장
int sharkSize = 2; //아기상어 크기 저장

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

bool eat = true; //마지막 남은 물고기가 자기 몸집보다 큰 물고기일 경우를 대비

int minLength = 98765432; //최단경로 저장
vector<pair<int, int>> minLoc;  // 최단 경로에 있는 물고기 위치 저장
int ans = 0;
int nowStack = 0; //현재까지 누적해서 먹은 물고기 수 저장

bool cmp (pair<int, int> a, pair<int, int> b) {
    if(a.first == b.first)
        return a.second<b.second;
    else return a.first<b.first;
}

// destX, destY에 있는 물고기가 최단 경로인지 확인
void minRoad(int startX, int startY, int destX, int destY, int cnt) {
    if((startX == destX) && (startY==destY)) {
        if(cnt < minLength) {
            minLength = cnt;
            minLoc.clear();
            minLoc.push_back(make_pair(destX, destY));
        }
        else if(cnt==minLength) {
            minLoc.push_back(make_pair(destX, destY));
        }
        return;
    }
    //visited[startX][startY] = true;
    for(int i=0; i<4; i++) {
        int newX = startX + dx[i];
        int newY = startY + dy[i];
        if(newX<0 || newX>=N || newY<0 || newY>=N || visited[newX][newY]) continue;
        if(board[newX][newY] <= sharkSize) {
            visited[newX][newY] = true;
            minRoad(newX, newY, destX, destY, cnt + 1);
            visited[newX][newY] = false;
        }
    }
}

// 최단경로 내에 있는 물고기 찾기
bool findFish() {
    bool check = false; //물고기를 찾았는지 못찾았는지 저장
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(i==sharkX && j==sharkY) continue;
            // 자기자신보다 작은 몸집의 물고기
            if(board[i][j] >= 1 && board[i][j]<=6 && (board[i][j] < sharkSize)){ //물고기 찾았으니까 최단경로 갱신해야 함
                check = true;
                minRoad(sharkX, sharkY, i, j, 0);
            }
        }
    }

    return check;
}

// 찾은 곳으로 가서 먹기
void go() {
    sort(minLoc.begin(), minLoc.end(), cmp);
    int newX = minLoc[0].first;
    int newY = minLoc[0].second;
    //cout<<minLoc.size()<<'\n';
    //cout<< board[newX][newY] << ' '<<sharkSize<<"\n";
    if(board[newX][newY] >= sharkSize && minLoc.size()==1)
        eat = false;

    //cout<<minLength<<"\n";
    ans += minLength;
    nowStack+=1;
    if (nowStack == sharkSize) {
        nowStack = 0;
        sharkSize+=1;
    }

    board[newX][newY] = 9;
    board[sharkX][sharkY] = 0;
    sharkX = newX, sharkY = newY;
}

void sol() {
    while(findFish() && eat) {
        eat = true;
        go();
        memset(visited, false, sizeof(visited));
        minLength = 98765432;
        minLoc.clear();
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    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){
                sharkX = i, sharkY=j;
            }
        }
    }
    sol();
    cout<<ans<<"\n";
}

 

재도전

재귀 함수도 그렇고, 물고기를 찾았을 때 최단 경로인지 확인하는 것을 물고기를 찾을 때마다 반복해서 시간초과가 나온 것 같다.

그래서 로직을 다음과 같이 변환했다.

1. 먹을 수 있는 물고기가 없을 때까지 다음 과정을 반복한다.
   1. 가장 가까운 곳에 있는 물고기를 찾기 위해 dist 배열 (아기 상어로부터의 거리) 갱신
   2. dist 배열을 보고, 가장 가까운 곳에 있는 물고기의 위치와 거리를 나타내는 minX, minY, minD 를 갱신
   3. 2에서 찾은 정보를 가지고 '물고기 먹음' 처리

//
// Created by ღ 𝚂𝚑𝚒𝚗𝚎 𝚈𝚎𝚘𝚗 ღ on 2022/10/11.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;

int N;
int board[21][21];
int dist[21][21];
int sharkX, sharkY; //아기상어 위치 저장
int sharkSize = 2; //아기상어 크기 저장

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

int minX = -1, minY = -1;
int minDist = 98765432; //최단경로 저장
vector<pair<int, int>> minLoc; // 먹을 수 있는 물고기 위치 저장
int ans = 0;
int nowStack = 0; //현재까지 누적해서 먹은 물고기 수 저장

bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.first==b.first)
        return a.second<b.second;
    else return a.first<b.first;
}

// 먹을 수 있는 물고기가 있는 경우 먹을 물고기를 선정 (minX, minY, minDist 갱신)
void targeting() {
    bool ret = false;
    // 먹을 수 있는 물고기가 있을 때 타겟 선정

    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            if(board[i][j] <sharkSize && board[i][j]!=0 && dist[i][j]!=-1 && dist[i][j] < minDist) {
                minDist = dist[i][j];
                minX = i, minY = j;
                //ret = true;
            }
        }
    }

    //return ret; // true 반환 시 물고기 선정된 것
}

// 지금 제일 가까운 공간에 먹을 수 있는 물고기 찾기
void BFS() {

    queue<pair<int, int>> q;
    q.push(make_pair(sharkX, sharkY));

    while(!q.empty()) {

        int nowX = q.front().first;
        int nowY = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int newX = nowX + dx[i];
            int newY = nowY + dy[i];

            if (newX < 0 || newX >= N || newY < 0 || newY >= N ||
            sharkSize < board[newX][newY] || dist[newX][newY] != -1)
                continue;

            //거쳐가는 공간마다 거리 갱신, 거쳐간 공간을 distLoc으로 벡터에 저장
            dist[newX][newY] = dist[nowX][nowY] + 1;
            q.push(make_pair(newX, newY));

            //if(sharkSize>board[newX][newY])
            //    minLoc.push_back(make_pair(newX, newY));

        }

    }
}

// 선정한 물고기 먹기
bool eat() {
    // minDist가 초기 98765432와 같은 수라면 갱신이 안 된 것임 (먹을 물고기가 없다는 뜻)
    if(minDist == 98765432) return false;

    sharkX = minX, sharkY = minY; // 해당 위치로 상어 이동
    nowStack+=1; // 먹었으니까 이제까지 먹은 물고기 수 +1
    board[minX][minY] = 0;
    if(nowStack == sharkSize) { //이제까지 먹은 물고기 수가 상어 크기와 같다면 상어 사이즈 커지게 해야함
        nowStack = 0;
        sharkSize+=1;
    }
    ans+=minDist;
    return true;
}

void sol() {
    while(1) {

        minDist = 98765432;
        minX=-1, minY=-1;
        memset(dist, -1, sizeof(dist));
        dist[sharkX][sharkY] = 0;
        //minLoc.clear();

        BFS();

        targeting();

        if(!eat()) break;

    }

}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    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){
                board[i][j] = 0;
                sharkX = i, sharkY=j;
                sharkSize=2;
            }
        }
    }
    sol();
    cout<<ans<<"\n";
}