백준 c++ 아기상어 19238 bfs

문제)

1)

 

 

먼저 이문제를 보자마자 생각이 든것은

 

1) BFS를 이용하고

2) 먹을 수 있는 생선을 찾으면 바로 생선의 크기 증가를 위한 cnt +1증가 시키고

3) cnt == fish_size(생선의 현재 크기) 같으면 생성 크기 증가시키고 cnt =0으로 셋팅

4) 방문한 모든 자리는 다시 0처리 먹은 생선 0으로 처리하기 

 

이렇게 생각하였다.

방향을 무시하고 했던것은 애초에 방향을 움직일 때 상 좌 우 하 순서로 움직인데만 주어진 조건을 만족하는줄 알았다.

하지만

이 예제에서 답이 잘못나오게 되었다. 여기서  문제는 상좌우하 순서로는 조건을 만족하지 못한다는것이였다.

가장 멍청한건.. 내 생각이 맞다고 생각하고 컴퓨터의 답을 무시한것.. 그렇게 시간을 버리고 같은 방법으로 코드를 다시 짜기 시작했다..

그렇게 시간을 엄청 허비하고 결국은 다른 사람의 코들르 참고하려고 하였으나.. 자존심이 허락하지 않아서... 틀린 부분에 대한 방문 순서를 비교하고서야.. 잘못된것을 알게되었습니다.

 

그래서 여기서 놓쳤던 부분을 이용해서 다시 생각을 하였습니다.

 

1) BFS를 이용하고

2) 먹을 수 있는 생선을 찾으면 같은 턴 즉 이동 거리가 같은 거리내에서 먹을 수 있는 모든 생선을 pq라는 우선순위 큐에 넣어주었다.

(왜냐하면 우선순위 큐에서 top이 같은 거리내에서 가장 상위 왼쪽에 존재하기 때문이다)

3-1) 같은 거리내의 탐색이 종료되면 pq가 비어있는지를 확인하고 비어있다면  origin_cir = cir로 바꾸어 주어 다시 먹을 수 있는 상어를 탐색하게 해준다

3-2)만약에 같은 거리내에서 먹을 수 있는 생선이 존재한다면 거리를 결과에 저장해주고 아래 코드와 같이 하게되면 문제를 해결할 수 있게됩니다. 

 

#include<iostream>

#include<vector>

#include<queue>

#include<cstring>

#include<functional>

#include<tuple>

using namespace std;

#define MAX_N 21

int N; //공간의 크기

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

int y_dir[4]={0,-1,1,0}; //상 좌 우 하.

int visited[MAX_N][MAX_N];

int map[MAX_N][MAX_N]; //어장의 크

int result;

priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;

queue<tuple<int,int,int>> q;

int cnt =0;

int origin_cir =0;

int fish_size =2;

void bfs();

int main(){

ios::sync_with_stdio(false);

cin.tie(NULL);

cout.tie(NULL);

cin >> N;

 

for(int i=1;i <=N;i++){

for(int j=1;j<=N;j++){

int a;

cin >> a;

map[i][j]=a;

if(a == 9){ //상어의 위치 입력받음.

q.push(make_tuple(i,j,0));

map[i][j]=0;

}

}

}

bfs();

cout<<result;

 

return 0;

}

void bfs(){

while(!q.empty()){

int x = get<0>(q.front());

int y = get<1>(q.front());

int cir = get<2>(q.front());

q.pop();// 같은 거리에 있는 거 찾기 위함

if(cir>origin_cir && pq.empty()==1){

origin_cir=cir;

}

if(cir>origin_cir && pq.empty()==0){

result += cir;

origin_cir=0;

cir=0;

cnt+=1;

if(cnt==fish_size){

cnt =0;

fish_size+=1;

}

while(!q.empty()){ q.pop();}

int xx = pq.top().first;

int yy = pq.top().second;

map[xx][yy]=0;

memset(visited,0,sizeof(visited));

visited[xx][yy]=1;

q.push(make_tuple(xx,yy,cir));

while(!pq.empty())pq.pop();

 

}else{

for(int i=0;i<4;i++){

int nx = x + x_dir[i];

int ny = y + y_dir[i];

if(nx >=1 && ny>=1 && nx<=N && ny<=N){

if(visited[nx][ny]==0 && map[nx][ny]>=0){

//방문하지 않은 물고이라면

 

if(map[nx][ny]==fish_size || map[nx][ny]==0){ //만약 크기가 같거나 0이면

visited[nx][ny]=1;

q.push(make_tuple(nx,ny,cir+1));

}else if(map[nx][ny]<fish_size && map[nx][ny]>0){

pq.push(make_pair(nx,ny));

visited[nx][ny]=1;

q.push(make_tuple(nx,ny,cir+1));

}

}

}

}

}

}

}

문제를 풀때 중요한건 조건을 간과하거나 무시하거나 쉽게 생각하지 말아야한다는걸.. 다시한번 깨닫게 되었습니다.