백준 16236번: 아기 상어 (C++)

문제 링크 : https://www.acmicpc.net/problem/16236

 

 

bfs문제입니다.

 

<전체적인 알고리즘>

  bfs로 먹을 수 있는 먹이를 계속 찾습니다. bfs가 끝날때 마다 먹이를 찾는데 걸리는 시간을 계속 더해줍니다. 

  만약 먹을 수 있는 먹이가 더이상 없다면 종료시켜줍니다.

 

<부연 설명>

  -  최단 거리의 먹이들 중 가장 위쪽에서 왼쪽인 먹이를 찾기위해 일단 최단 거리의 먹이를 전부 저장해야함

         -> 처음 먹이를 찾을때의 거리(최단 거리)를 저장한 후 거리가 더 커지기 전까지의 먹이를 전부 저장한다.

              (bfs는 가까운 것부터 탐색하므로 거리가 같은 부분끼리 뭉쳐서 queue에 저장된다.)

 

<자료 구조>

  - 상어 정보를 저장하는 class (저장해야 하는 속성이 3개 이상이라 class를 정의함)

  - 같은 거리의 먹이들을 임시저장하기위한 vector

  

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130

#include<iostream> #include<queue> #include<vector>   using namespace std;   int map[22][22]; int baby_x, baby_y;    //아기상어 위치 int baby_size=2;       //아기상어 크기 int baby_prey = 2;     // 진화하려면 먹어야 하는 먹이 개수 bool check[22][22]; int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; int n;   class ins { public:     int x, y, count;     ins(int x, int y, int count)     {         this->x = x;         this->y = y;         this->count = count;     } };   int bfs(int startx, int starty) {     queue<ins> q;     vector < pair<int, int>> v;     fill(&check[0][0], &check[19][20], 0);     q.push(ins(startx, starty, 0));     check[startx][starty] = true;       int result_count = -1;           while (!q.empty())     {         int x = q.front().x;         int y = q.front().y;         int count = q.front().count;   //거리         q.pop();           if (map[x][y]>0&&map[x][y] < baby_size)  //먹을 수 있을때         {             if (result_count == -1)  //처음 먹이 발견할때의 거리 저장             {                 result_count = count;                       }                                 if(result_count<count) break;  // 먹이 처음 발견했을때 count보다 count가 커지면 탈출                   v.push_back(make_pair(x, y)); //가장 가까운 먹이들 저장         }           for (int d = 0; d < 4; d++)         {             int nextx = x + dir[d][0];             int nexty = y + dir[d][1];             if (nextx < 0 || nexty < 0 || nextx >= n || nexty >= n)continue;             if (check[nextx][nexty])continue;             if (map[nextx][nexty] > baby_size)continue;             check[nextx][nexty] = true;               q.push(ins(nextx, nexty, count + 1));         }     }       if (v.empty())return -1; // 먹이가 없으면 -1반환       int tmp_x = v[0].first;     int tmp_y = v[0].second;     for (int i = 1; i < v.size(); i++)   //같은 거리중 가장 위에서 왼쪽 먹이 찾기     {         int x = v[i].first;         int y = v[i].second;           if (tmp_x > x)         {             tmp_x = x; tmp_y = y;         }         else if (tmp_x == x&&tmp_y>y)         {             tmp_x = x; tmp_y = y;         }     }     baby_x = tmp_x;     baby_y = tmp_y;     map[baby_x][baby_y] = 0;       baby_prey--;  //먹음     if (baby_prey == 0)  // 진화까지 필요한 먹이가 0이라면 진화     {         baby_size++;         baby_prey = baby_size;     }       return result_count; }   int main() {     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)             {                 baby_x = i;                 baby_y = j;                 map[i][j] = 0;             }         }     }       int time = 0;           while (1)     {         int plus_time=bfs(baby_x,baby_y);   //먹이 찾기         if (plus_time==-1)break;   //더이상 먹을게 없으면 종료         else time += plus_time;    //먹는데 걸린 시간 추가     }           cout << time;       return 0; }

 

궁금하신 점은 댓글에 남겨주시면 답변드리겠습니다.