Life Engineering
[BOJ 16236] 아기 상어 (C++) 본문
https://www.acmicpc.net/problem/16236
#include <bits/stdc++.h>
using namespace std;
int dy[4]={0,0,1,-1};
int dx[4]={1,-1,0,0};
int space[20][20];
int minVal=987654321;
class Pos{
public:
int y;
int x;
int cnt;
Pos(int y, int x, int cnt){
this->y=y;
this->x=x;
this->cnt=cnt;
}
};
pair<int,int> bfs(int shark_y, int shark_x, int shark_size, int N){
bool visited[N][N];
queue<Pos> q;
pair<int,int> d=make_pair(30,30);
minVal=987654321;
for (int i=0; i<N; i++){
for (int j=0; j<N; j++){
visited[i][j]=false;
}
}
q.push(Pos(shark_y, shark_x, 0));
visited[shark_y][shark_x]=true;
while (!q.empty()){
Pos p=q.front();
q.pop();
for (int i=0; i<4; i++){
int ny=p.y+dy[i];
int nx=p.x+dx[i];
if (nx<0 || ny<0 || nx>=N || ny>=N){
continue;
}
if ((space[ny][nx]==0 || space[ny][nx]==shark_size) && visited[ny][nx]==false){
visited[ny][nx]=true;
q.push(Pos(ny,nx,p.cnt+1)); //이동할 수 있으면 탐색
}
else if (space[ny][nx]>=1 && space[ny][nx]<shark_size && visited[ny][nx]==false){ //먹을 수 있는 물고기이면 pq에 넣음
visited[ny][nx]=true;
if (p.cnt+1<minVal){
minVal=p.cnt+1;
d.first=ny;
d.second=nx;
}
else if (p.cnt+1==minVal){
if (ny<d.first){
d.first=ny;
d.second=nx;
}
else if (ny==d.first){
if (nx<d.second){
d.first=ny;
d.second=nx;
}
}
}
}
}
}
return d;
}
int main(){
int N, x;
int answer=0;
int num=0;
cin>>N;
int shark_y, shark_x;
int shark_size=2;
for (int i=0; i<N; i++){
for (int j=0; j<N; j++){
cin>>x;
space[i][j]=x;
if (x==9){
shark_y=i;
shark_x=j;
}
}
}
while (true){
pair<int,int> p=bfs(shark_y, shark_x, shark_size, N);
if (p.first==30){
break;
}
space[shark_y][shark_x]=0; //기존에 있던 곳 0으로
shark_y=p.first;
shark_x=p.second;
num++;
if (num==shark_size){
shark_size+=1;
num=0;
}
space[shark_y][shark_x]=0;
answer+=minVal;
}
cout<<answer<<"\n";
return 0;
}
비효율적으로 푼듯..
일단, bfs 로 탐색하다가 이동할 수 있으면=>계속 큐에 넣어서 이동한다.
만약 아기상어가 먹을 수 있는 것이면 => minValue와 비교하고, minValue 와 같을 경우에는 가장 위에, 가장 왼쪽에 있는 애를 반환하도록 한다.
탐색이 끝나고 큐가 종료되면 아기상어가 먹은 자리를 0으로 해주고, 아기상어의 자리를 갱신해주고 또 bfs 를 돌리는 식이다.
반복문의 종료는 bfs 함수가 더이상 새로운 좌표를 반환하지 않았을 때 종료한다.
그런데 이렇게 하니까 따져줘야 될 것도 번거롭게 많다..
이 분의 코드를 참고하니,
priority_queue 를 사용해서 이동할 수 있는 애들을 큐에 모두 다 집어넣어준다.
(미방문이고, 아기 상어의 크기보다 작은 애들이거나 0 인 애들)
priority_queue 는 우선적으로 count가 작은 애들이고, count 가 같을 경우엔 가장 위, 가장 왼쪽에 있는 애들이 큐의 앞쪽에 위치한다.
이렇게 하면 자동적으로 조건에 맞는 아기상어의 먹이가 튀어나올 수 있다.
큐에서 아이템을 하나뺄때는, 아기상어의 먹이가 될 수 있는 것이면(0을 초과 하고, 아기상어의 크기보다 작은) 그 위치에 0 처리를 해주고, 크기 조건을 만족하면 크기를 늘려주고, 이제 이 priority_queue 에 대해서는 탐색을 하지 않아도 되므로(먹이를 찾았으니 이제 새롭게 움직여야하니) 큐를 모두 비워주고, 이 새로운 위치에 대해서 다시 bfs 탐색을 하는 식이다!!
struct a{
int d, x,y;
bool operator < (const a &t) const{
...
}
};
이런 식으로 구현해주고, 큐에는 q.push({1,2,3}) 이런 식으로 넣어주면 자동적으로 min-heap 구조로 아이템이 튀어나오게 된다.
내 코드는 아기상어의 먹이를 찾았더라도 혹시 모를 또다른 최소값을 위해 계속 bfs 를 돌린다.. 비효율적이다.. 시간초과는 나지 않았지만 말이다.
핵심은, 우선순위 큐를 이용한 BFS 를 이용해, 바로 조건에 맞는 먹이가 튀어나오도록 하며 그 먹이가 나왔을 때는 그걸 기준으로 다시 bfs 를 돌린다는 것!
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 타겟 넘버 (C++) (0) | 2021.09.23 |
---|---|
[프로그래머스] 소수 찾기 (C++) (0) | 2021.09.22 |
[프로그래머스] 단체사진 찍기 (C++) (0) | 2021.09.16 |
[프로그래머스] 신규 아이디 추천 (C++) (0) | 2021.09.16 |
[프로그래머스] 메뉴 리뉴얼 (C++) (0) | 2021.09.14 |