[백준] 16236. 아기상어

[문제]

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

16236번: 아기 상어

 

 

[풀이]

 

아기 상어와 물고기가 존재. 

아기 상어는 자신보다 작은 물고기들을 잡아먹을 수 있다.

아기 상어는 자신보다 큰 물고기가 존재하는 칸은 지나가지 못한다.

아기 상어는 1칸 움직이는데 1초 걸린다.

아기 상어가 자신의 크기만큼 물고기를 먹는다면 크기가 1 증가한다.

( 크기가  3인 상어가 물고기 3마리를 먹으면 크기가 4가 된다.)

 

입력으로는 공간의 크기와 상태가 주어진다.

아기 상어가 먹을 수 있는 물고기들을 모두 먹을 때까지 걸리는 시간을 구해서 출력하면 된다.

 

BFS를 사용해 아기 상어의 좌표를 기준으로 visited에 아기 상어와 현재 좌표 사이의 거리를 저장했다.

이 때 공간의 범위를 벗어나거나, 이미 상어가 지나간 곳이거나, 상어보다 큰 물고기가 존재하는 곳은 그냥 지나친다.

 

물고기가 존재하고 물고기의 크기기 상어의 크기보다 작고

거리를 기준으로 현재 최소 거리보다 더 가깝다면 

잡아먹을 물고기의 좌표를 저장해놓은 tx,ty와 최소 거리인 len을 update

 

 

 

[코드]

 

시간 : 0ms

 

- 최소 거리 구하는 부분 ( 60번째 line)

원래 if( nx <= tx && ny <= ty)로 했더니 시간이 4ms 나와서 바꿔줬다. 

 

#include <iostream>
#include <queue>

#define MAX 20
using namespace std;

struct INFO{
    int x,y,size;
    
};
struct pos{
    int x,y;
};

INFO shark;

int total=0;
int N,M;
int map[MAX][MAX]={0,};


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


bool BFS()
{
    int visited[MAX][MAX]={0,};
    int tx,ty;
    
    int len = 1e9;
    
    queue <pos> q;
    q.push({shark.x , shark.y});
    
    while(!q.empty()){
        int x= q.front().x;
        int y= q.front().y;
        
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx <0 || ny < 0 || nx >= N || ny >= N)   continue;
            if(visited[nx][ny] != 0)    continue;
            if(map[nx][ny] > shark.size)    continue;
            
            visited[nx][ny] = visited[x][y]+1;
            q.push({nx,ny});
            
            if(map[nx][ny] != 0 && map[nx][ny] < shark.size){
                if(len > visited[nx][ny]){
                    tx = nx;
                    ty = ny;
                    len = visited[nx][ny];
                }
                else if(len == visited[nx][ny]){
                    if(nx <tx){
                        tx = nx;
                        ty = ny;
                    }
                    else if(nx == tx){
                        if(ny < ty){
                            tx = nx;
                            ty = ny;
                        }
                    }
                }
            }
        }
    }
    if(len ==1e9) return false;
    map[tx][ty]=0;
    shark.x = tx;
    shark.y = ty;
    total+= len;
    return true;
}

int main(void)
{
    scanf("%d",&N);
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            scanf("%d",&map[i][j]);
            if (map[i][j]==9){
                INFO info = {i,j,2};
                shark = info;
                map[i][j]=0;
            }
        }
    }
    int cnt =0;
    while(1)
    {
        if(BFS()){
            cnt++;
            if(cnt == shark.size){
                shark.size++;
                cnt=0;
            }
        }
        else break;
    }
    printf("%d",total);
    
    return 0;
    
}

 

지적, 조언, 질문 환영입니다.

댓글 남겨주세요~