백준 17142번: 연구소 3 (C++)

문제 링크 : www.acmicpc.net/problem/17142

 

 

<전체적인 알고리즘>

1. 바이러스가 있는 지점들을 모두 vector에 넣어주고 dfs로 m개의 모든 조합을 선택한다.

2. m개의 바이러스를 선택했으면 spread_bfs로 바이러스를 퍼뜨려준다.

3. 바이러스를 퍼뜨리며 시간을 위치에 기록한다.

4. 이차원 배열에 0이 존재하면 스킵, 다 퍼졌으면 최대시간을 반환한다.

5. 2,3,4를 반복하며 최소시간을 구한다.

 

 

<주의 사항>

바이러스가 퍼진 시간을 구할 때,,바이러스가 빈 공간에만 모두 퍼진시간을 구하는 것이다. 

즉 아직 비활성 상태의 바이러스에 더욱 퍼질 수 있어도 이미 빈공간에 다 퍼졌으면 그것이 최소시간이다.

 

<전체 코드>

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

#include<iostream> #include<vector> #include<queue>   using namespace std;   int n; int map[52][52]; vector<pair<int, int>> start_virus; int dir[4][2] = { {-1,0},{0,1},{1,0},{0,-1} }; bool check[52][52]; int answer = 987654321;   class ins { public:     int x, y, count;     ins(int x, int y, int count)     {         this->x = x;         this->y = y;         this->count = count;     } };   int spread_bfs()        //바이러스 퍼뜨려보기 {     fill(&check[0][0], &check[49][50], 0);     int tmp[52][52];     for (int i = 0; i < n; i++)     {         for (int j = 0; j < n; j++)         {             tmp[i][j] = map[i][j];  //퍼뜨려볼 임시 맵 복사         }     }       queue<ins> q;     for (int i = 0; i < start_virus.size(); i++)     {         int x = start_virus[i].first;         int y = start_virus[i].second;         q.push(ins(x,y,1));         tmp[x][y] = 1;         check[x][y] = true;     }       while (!q.empty())     {         int x = q.front().x;         int y = q.front().y;         int count = q.front().count;         q.pop();           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 (tmp[nextx][nexty] == 1)continue;             if (check[nextx][nexty])continue;             check[nextx][nexty] = true;                           if (tmp[nextx][nexty] == 0)  //빈 방이면 시간 넣어주기             {                 tmp[nextx][nexty] = count + 1;             }             q.push(ins(nextx, nexty, count + 1));         }     }     int maxx = 0;     for (int i = 0; i < n; i++)     {         for (int j = 0; j < n; j++)         {             if (tmp[i][j] == 0)return -1;  //빈 공간있으면 -1반환             maxx = max(tmp[i][j], maxx);  //최대 시간         }     }     return maxx-1; // 다 퍼진 시간 반환 }   void dfs(int count,int start,vector<pair<int,int>> &virus)  //바이러스 놓을 수 있는 곳 m개 조합으로 놓기 {     if (count == 0)  //시작 바이러스 m개 선택 했으면,,     {         int result=spread_bfs();  //퍼뜨려보기         if (result != -1) answer = min(answer, result);         return;     }     for (int i = start; i < virus.size(); i++)     {         start_virus.push_back(virus[i]);         dfs(count - 1, i + 1, virus);         start_virus.pop_back();     }   }   int main() {     ios_base::sync_with_stdio(false);     cin.tie(0);       int m;     cin >> n >> m;     vector<pair<int,int>> virus;     for (int i = 0; i < n; i++)     {         for (int j = 0; j < n; j++)         {             cin >> map[i][j];             if (map[i][j] == 2)             {                 virus.push_back(make_pair(i, j));  //바이러스 놓을 수 있는 곳 저장                 map[i][j] = -1;             }         }     }           dfs(m, 0, virus);     if (answer == 987654321)answer = -1;     cout << answer;           return 0; }

 

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