아기상어_16236

문제 출처 : 아기상어_16236

파라미터 정리

NxN 공간 (2~20)
M 물고기 수
아기상어 1마리, 처음 크기 2, 1번에 1칸 이동(상하좌우 中 1)

물고기<상어 : 먹기, 지나가기
물고기=상어 : 지나가기
물고기>상어 : 모두 불가능

-먹을 수 있는 물고기 無 : 프로그램 종료
-먹을 수 있는 물고기 有 : 가까운 물고기 먼저 접근, 우선 순위(가장 위에 있는 물고기 -> 가장 왼쪽에 있는 물고기, 상 좌 우 하)

크기만큼 물고기 먹으면 크기+1
ex) 크기가 3인 아기상어는 물고기 3번 먹은 후 크기 4가 됨

0 : 빈칸
1~6 : 셀에 있는 물고기의 크기
9 : 아기 상어의 위치

간략한 과정

Map[20][20]의 정보 입력받음
아기 상어의 위치값 저장함
Map의 값 중 아기 상어의 크기보다 작은 물고기가 있으면 거리를 저장함
거리의 최솟값과 row, col 정보를 저장함
최솟값이 같을 때에는 r,c 값을 비교해서 선정함
Map이 끝나면 마지막 최솟값으로 아기 상어 이동하고 먹은 갯수 카운팅
먹은 갯수 == 아기 상어 크기 이면 아기상어 크기+1
가능한 물고기가 없을 때까지 반복함
총 이동한 거리를 반환함

코드

#include <iostream>
#include <queue>

using namespace std;

#define INF 98456545

struct Fish{
    int r, c, d;
};

int N;
int Map[20][20];
int Dr[4] = {-1, 0, 0, 1};
int Dc[4] = {0, -1, 1, 0};
Fish shark;

int solve(){

    int res = 0;
    int age = 2;
    int cnt = 0;
    
    do{
        bool visited[20][20] = {false};
        queue<Fish> n_pos;
        n_pos.push({shark.r, shark.c, 0});
        visited[shark.r][shark.c] = true;
        shark.d = INF;
        
        while(!n_pos.empty()){
            Fish curr = n_pos.front();
            n_pos.pop();
            
            if(curr.d > shark.d) break;
            if(Map[curr.r][curr.c] > age) continue;
            if(Map[curr.r][curr.c] != 0 && Map[curr.r][curr.c] < age){
                if(curr.d < shark.d){//가장 짧은 거리
                    shark = curr;
                }else if(curr.d == shark.d){//거리 같을 때 우선순위 고려하기
                    if(curr.r < shark.r)//현재 물고기가 저장된 물고기 보다 위에
                        shark = curr;
                    else if(curr.r == shark.r && curr.c < shark.c)
                    //같은 높이일때 현재 물고기가 더 왼쪽에 있을 때
                        shark = curr;
                }
                continue;
            }
            
            for(int i = 0; i < 4; i++){
                int nr = curr.r + Dr[i], nc = curr.c + Dc[i];
                if(visited[nr][nc] == true) continue;
                if(nr < 0 || nc < 0 || nr > N-1 || nc > N-1) continue;
                visited[nr][nc] = true;
                n_pos.push({nr, nc, curr.d+1});
            }
        }
    
        if(shark.d != INF){
            res += shark.d;
            cnt++;
            if(cnt == age){
                age++;
                cnt = 0;
            }
            Map[shark.r][shark.c] = 0;
        }
        
    }while(shark.d != INF);
    
    return res;
}

int main()
{
    int x,y;
    
    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){
                Map[i][j] = 0;
                shark = {i, j, 0};
            }
               
        }
    }
    
    cout << solve() << endl;

    return 0;
}

시행착오

물고기 위치 저장해서 거리 구하기
물고기 위치를 벡터로 저장해서 모든 벡터에 대해서 거리구하기
이렇게 하면 지나갈 수 없는 부분을 체크하기가 힘듦
만약에 물고기가 400마리일 경우 더 비효율적인 것 같음

우선 순위대로 가까운 곳부터 접근해서 물고기 찾기
위 왼쪽 오른쪽 아래 순서로 접근
하다가 포기,,,나중에 다시 도전하기

물고기, 상어(r, c, age)로 저장해두기
상어 나이보다 작은 물고기를 새로운 벡터에 넣고 벡터 끝날 때까지 거리 비교함, 거리가 가장 가까운 순서로 먹고 이때 cnt더해주기, 거리가 같을 때에는 r,c 비교하기, 먹을 때 마다 개수를 세고 상어의 나이와 비교하고 나이가 바뀌면 새로운 먹이 벡터 만들기, 상어의 먹이 벡터가 없을 때 까지 진행한다.

시행착오

1. BFS 탐색 + Queue 사용하기
   Queue에 방문하지 않은 곳 입력하기
   BFS 탐색을 이용해서 queue의 주변 탐색하기
   이동한 거리 계산해서 가장 가까운 물고기 찾기
   거리가 같을 경우 row, col 비교하기
   물고기 먹은 횟수 카운트 해서 상어 크기 키우기
2. 예제 4번 돌렸을 때 56나옴,, 다른 부분은 다 맞음
   -> 40번째 줄에서 curr.r을 res와 비교해서 문제가 있었음
   -> res를 shark.d로 수정해서 고쳐짐