출처 : https://www.acmicpc.net/problem/14502
연구소 성공 풀이
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 3709 | 2029 | 1358 | 55.633% |
문제
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.
2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
이 때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.
2 1 0 0 1 1 0 1 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
바이러스가 퍼진 뒤의 모습은 아래와 같아진다.
2 1 0 0 1 1 2 1 0 1 0 1 2 2 0 1 1 0 1 2 2 0 1 0 0 0 1 2 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최대값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
예제 입력
7 7 2 0 0 0 1 1 0 0 0 1 0 1 2 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0
예제 출력
27
예제 입력 2
4 6 0 0 0 0 0 0 1 0 0 0 0 2 1 1 1 0 0 2 0 0 0 0 0 2
예제 출력 2
9
예제 입력 3
8 8 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 2 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
예제 출력 3
3
힌트
>> 풀이 방법
이 풀이에서는 '그냥 모두 뒤지는 것이 빠르다. ' 라는 판단을 했다.
왜냐하면 배열의 크기가 매우 작고 (최대 8*8) 벽을 3개를 세우기 때문에 최대 선택한 배열의 개수는 64C3이고
8*8* 64C3 를 해도 속도에 영향을 미칠 정도는 아니라고 생각했다.
(사실 실제 풀이에는 이 정도로 계산하지는 않고, 적으니까 가도 되겠다라고 생각했는데 더 엄밀하게 풀려면 계산을 필수로 먼저 해야겠다. )
풀이방법은 이렇다.
벽을 어떻게 전진시켜야 할까??
벽 3개를 선택하면 반드시 1,2,3 순서로 이루어져있다.(중복이 없고, 순차적으로 나열 가능하다)
마지막에 있는 벽의 index부터 하나씩 늘려주다가, 끝점에 도달하면 다른 점도 index를 수정하여 64C3 개 만큼 벽을 세우는 경우를 조사한다.
index를 하나 늘릴 때에는 기존 로우*M + 기존 컬럼 + 1 을 이용하면 간단하게 할 수 있다.
3번째 벽이 끝에 도달했을 경우에는 2번째 벽의 index를 증가시켜주고, 2번째 벽의 바로 다음으로 3번째 벽을 배치한다.
이 때, 점 1개가 끝에 도달한 것과 점 2개가 끝에 도달한 것은 다르게 적용된다.
가령 2와 3벽이 모두 끝에 도달하면 1벽도 한 칸 전진하고, 2와 3은 1의 바로 옆에 붙어야 한다.
벽에 몇 개가 도달했는지 구분하기 위해서 isEnd 변수를 사용한다.
isEnd는 끝에 도달한 벽의 개수를 저장하는 함수이다.
1이면 3번 벽만 끝에 도달, 2이면 2,3번 벽이 끝에 도달, 3이면 모두 끝에 도달한다.
isEnd가 3이면 모든 점이 끝에 도달했기 때문에, while문을 종료하고 답을 출력한다.
그렇다면 현재 바이러스가 감염되지 않은 구간을 검사하는 함수는 어떻게 짤까?
해당함수는 26라인의 howManySafe()함수이다.
모든 배열을 검사를 하면서 2인 구간을 찾는다.
2인 구간을 찾으면 queue에 넣는다. (bfs를 수행한다.)
queue의 사이즈가 0일때까지, 하나씩 빼면서 3으로 바꾼다.(3은 바이러스가 퍼진 구간이면서 들린 구간 역할을 한다)
하나씩 빼면서 인근에 있는 4개의 영역에 바이러스가 퍼질 수 있는지 검사한다.
검사하고 가능한 영역은 queue에 다시 넣어준다.
이런식으로 bfs를 수행하면 값을 구할 수 있고 answer_sub 벡터에 넣어준다.
모든 벽에 대한 bfs로 검증이 끝나면 answer_sub를 정렬하여 마지막에 있는 원소를(가장 큰 원소) 정답으로 간주하고 출력한다.
>> 다른 참고할 풀이
- 다른 풀이 중에 벽을 세울 때, dfs를 활용한 풀이가 있었다.
>> 소스코드
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 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 | #include <iostream> #include <vector> #include <algorithm> #include <queue> #define POINT_NUM 3 using namespace std; int N, M; int** labotory; int** sub_labotory; vector<int> answer_sub; pair<int,int> point_arr[POINT_NUM]; int side_row[4] = {-1, 0, 1, 0}; int side_col[4] = { 0, 1, 0,-1}; void print_arr(){ for( int i = 0 ; i < N ; i++){ for ( int j = 0 ; j < M ; j ++){ printf("%d " ,sub_labotory[i][j]); } printf("\n"); } printf("\n"); } int howManySafe(){ int answer = 0; queue<pair<int, int>> sub_queue; // 2를 찾고 찾으면 주변에 있는 놈들을 가능한 한 모두 바꿔준다. for( int i = 0 ; i < N ; i++){ for ( int j = 0 ; j < M ; j ++){ // 만약 2라면, 주변 가능한 영역을 모두 바이러스로 채워본다. if(sub_labotory[i][j] == 2){ sub_queue.push({i,j}); // bfs로 수행 while(sub_queue.size()){ pair<int,int> now_position = sub_queue.front(); sub_queue.pop(); // 1이면 무시 if (sub_labotory[now_position.first][now_position.second] == 1 || sub_labotory[now_position.first][now_position.second] == 3) continue; // 검사한 영역은 3으로 변경 sub_labotory[now_position.first][now_position.second] = 3; // 상하좌우 다 queue로 넣기 for ( int k = 0 ; k < 4 ; k++){ int sub_row, sub_col; sub_row = now_position.first + side_row[k]; sub_col = now_position.second + side_col[k]; if ( (0<=sub_row) & (sub_row<N) & (0<=sub_col) & (sub_col<M) ) sub_queue.push({sub_row, sub_col}); } } } } } // 0 개수 검사 for (int i = 0 ; i < N ; i++) for ( int j = 0 ; j < M ; j++) if (sub_labotory[i][j] == 0) answer++; return answer; } int main(){ // 입력을 받는다. cin >> N >> M; // 배열 동적 생성 labotory = (int**)malloc(sizeof(int*)*N); sub_labotory = (int**)malloc(sizeof(int*)*N); for (int i = 0 ; i < N ; i++){ labotory[i] = (int*)malloc(sizeof(int)*M); sub_labotory[i] = (int*)malloc(sizeof(int)*M); } // 배열 값 넣기 for (int i = 0 ; i < N ; i++){ for ( int j = 0 ; j < M ; j++){ scanf("%d", &labotory[i][j]); } } // 처음 시작 영역 3개를 선택한다. point_arr[0] = {0,0}; point_arr[1] = {0,1}; point_arr[2] = {0,2}; // while 문의 flag비트 int isOver = 0; while(!isOver){ // 배열 복사 for (int i = 0 ; i < N ; i++){ for ( int j = 0 ; j < M ; j++){ sub_labotory[i][j]= labotory[i][j]; } } // 현재 포지션의 숫자가 적절한지 검사 (모두 0이어야한다) // 적절하면 안전 영역 개수를 검사한 후 정답 후보에 밀어 넣기 if (!(sub_labotory[point_arr[0].first][point_arr[0].second] | sub_labotory[point_arr[1].first][point_arr[1].second] | sub_labotory[point_arr[2].first][point_arr[2].second] )){ sub_labotory[point_arr[0].first][point_arr[0].second] = 1; sub_labotory[point_arr[1].first][point_arr[1].second] = 1; sub_labotory[point_arr[2].first][point_arr[2].second] = 1; int safe_area = howManySafe(); answer_sub.push_back( safe_area ); } // 다음 단계로 int isEnd = 0; // 끝인지 검사(끝점부터) for( int i = 0 ; i < POINT_NUM ; i++){ if ( (point_arr[POINT_NUM - 1 - i].first * M + point_arr[POINT_NUM - 1 - i].second) == N*M-1-i ) isEnd++; } // 하나씩 다음 단계로 넘어간다. switch (isEnd) { case 3: isOver = 1; break; default: point_arr[POINT_NUM - isEnd - 1] = { (point_arr[POINT_NUM - isEnd - 1].first*M + point_arr[POINT_NUM - isEnd - 1].second + 1)/M, (point_arr[POINT_NUM - isEnd - 1].first*M + point_arr[POINT_NUM - isEnd - 1].second + 1)%M }; for ( int i = 1 ; i < isEnd + 1; i++){ point_arr[POINT_NUM - isEnd - 1 + i ] = { (point_arr[POINT_NUM - isEnd - 1].first*M + point_arr[POINT_NUM - isEnd - 1].second + i)/M, (point_arr[POINT_NUM - isEnd - 1].first*M + point_arr[POINT_NUM - isEnd - 1].second + i)%M }; } break; } } sort(answer_sub.begin(), answer_sub.end()); printf("%d", answer_sub.back()); return 0; } | cs |