[문제]
https://www.acmicpc.net/problem/16236
16236번: 아기 상어
N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가��
www.acmicpc.net
[풀이]
아기 상어와 물고기가 존재.
아기 상어는 자신보다 작은 물고기들을 잡아먹을 수 있다.
아기 상어는 자신보다 큰 물고기가 존재하는 칸은 지나가지 못한다.
아기 상어는 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;
}
지적, 조언, 질문 환영입니다.
댓글 남겨주세요~
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] 17143. 낚시왕 (0) | 2020.10.02 |
|---|---|
| [백준] 4195. 친구 네트워크 (0) | 2020.10.01 |
| [백준] 16235. 나무 재테크 (0) | 2020.09.30 |
| [백준] 16234. 인구이동 (0) | 2020.09.28 |
| [백준]15683. 감시 (0) | 2020.09.21 |
