[BOJ] 18809.Gaaaaaaaaaarden(부분집합, BFS)

#. Problem

https://www.acmicpc.net/problem/18809

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

 

부분집합과 BFS로 풀리는 문제다.

먼저 최대 N과 M은 50으로,

아무리 최악의 경우라도 6,250,000번의 연산이 이루어지므로 완전탐색이 가능하다.

시뮬레이션 문제라서 문제를 풀기 전 어떻게 풀어갈지 정리가 필요하다.

먼저 필요한 정보를 뽑아보자.

* 배양액을 뿌릴 수 있는 땅은 미리 정해져있다.

* 배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼져간다.

* 초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 땅에서는 두 배양액이 합쳐져서 꽃이 피어난다. 

   꽃이 피어난 땅에서는 배양액이 사라지기 때문에 더 이상 인접한 땅으로 배양액을 퍼트리지 않는다.

* 모든 배양액을 남김없이 사용해야 한다.

* 모든 배양액은 서로 다른 곳에 뿌려져야 한다.

* 정원과 두 배양액의 개수가 주어져있을 때 피울 수 있는 꽃의 최대 개수

자, 그럼 가장 먼저 해야할 일은

1. 배양액을 뿌릴 수 있는 곳에 빨간색, 초록색 배양액을 뿌려줘야 한다.

   이 때, 부분집합을 활용해야한다.

2. 모든 배양액이 사용되었다면, 배양액이 뿌려진 좌표로부터 배양액을 퍼뜨려보자.

3. 배양액은 매 초마다 이전에 배양액이 도달한 적이 없는 인접한 땅으로 퍼진다.

4. 초록색 배양액과 빨간색 배양액이 동일한 시간에 도달한 땅에서는 두 배양액이 합쳐져서 꽃이 피어난다고 했다.

   초록색 배양액을 먼저 퍼뜨려보고, 빨간색 배양액을 퍼뜨리면서 동일한 시간에 초록색 배양액이 떨어진 땅이 있다면

   그 곳에 꽃이 피게 해주자.

   + 꽃이 피아난 땅애서는 더 이상 인접한 땅으로 배양액이 퍼지지 않는다.

5. 이렇게 count된 꽃의 최대 개수를 구하면 된다.

#. Code

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 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172

import java.awt.Point; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer;   public class BOJ18809 {       static int N, M, G, R, res, allDrop, map[][];     static int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};     static ArrayList<Point> area;     static State[] select;     static class State {         int x, y;         int color;    // 1: 초록, 2: 빨강                  public State(int x, int y, int color) {             super();             this.x = x;             this.y = y;             this.color = color;         }     }          public static void main(String[] args) throws IOException {                  BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());              N = Integer.parseInt(st.nextToken());    // 행         M = Integer.parseInt(st.nextToken());    // 열         G = Integer.parseInt(st.nextToken());    // 초록색 배양액 개수         R = Integer.parseInt(st.nextToken());    // 빨간색 배양액 개수         allDrop = G + R;    // 전체 배양액 개수         map = new int[N][M];         select = new State[allDrop];    // 배양액이 뿌려질 좌표 저장         area = new ArrayList<>();    // 배양액을 뿌릴 수 있는 좌표들 저장         // 정원 정보 입력         for (int i = 0; i < N; i++) {             st = new StringTokenizer(br.readLine());             for (int j = 0; j < M; j++) {                 map[i][j] = Integer.parseInt(st.nextToken());                 // 배양액을 뿌릴 수 있는 땅을 저장                 if(map[i][j] == 2) area.add(new Point(i, j));             }         }              go(0, 0, 0, 0);         System.out.println(res);     }       /**      * 배양액 뿌리기      * @param idx    배양액을 뿌릴 수 있는 좌표 index      * @param cnt    현재까지 뿌린 배양액의 갯수      * @param cntG    현재까지 뿌린 초록 배양액의 갯수      * @param cntR  현재까지 뿌린 빨강 배양액의 갯수      */     private static void go(int idx, int cnt, int cntG, int cntR) {         // 모든 배양액을 사용했을 경우         if(cnt == allDrop) {             // 배양액이 퍼져나간다.             // 피울 수 있는 꽃의 최대 개수             res = Math.max(res, spread());             return;         }         if(idx == area.size())              return;                  Point now = area.get(idx);                  // 여기에 초록색 배양액 뿌리기         if(cntG < G) {             select[cnt] = new State(now.x, now.y, 1);             go(idx + 1, cnt + 1, cntG + 1, cntR);         }                  // 여기에 빨간색 배양액 뿌리기         if(cntR < R) {             select[cnt] = new State(now.x, now.y, 2);             go(idx + 1, cnt + 1, cntG, cntR + 1);         }                  // 여기에 아무것도 뿌리지 않기         go(idx + 1, cnt, cntG, cntR);     }       // 배양액 퍼뜨리기     private static int spread() {                          // 배양액이 퍼지는데 걸린 시간 저장         int[][] visitedGrn = new int[N][M];         int[][] visitedRed = new int[N][M];                  int cnt = 0;         // 먼저 큐에 배양액이 뿌려져있는 좌표를 넣고         Queue<State> green = new LinkedList<>();         Queue<State> red = new LinkedList<>();         for (int i = 0; i < allDrop; i++) {             State tmp = select[i];             // 배양액에 뿌려진 곳은 1로 초기화             if(select[i].color == 1) {                 green.add(new State(tmp.x, tmp.y, tmp.color));                 visitedGrn[tmp.x][tmp.y] = 1;             }             else {                 red.add(new State(tmp.x, tmp.y, tmp.color));                 visitedRed[tmp.x][tmp.y] = 1;             }         }                  // 배양액이 모두 퍼질 때까지         while(!green.isEmpty() || !red.isEmpty()) {                          // 초록색 배양액부터 퍼진다.                         int size = green.size();             for (int s = 0; s < size; s++) {                 State now = green.poll();                 // 꽃이 핀 자리라면 pass                 if(visitedGrn[now.x][now.y] == -100) continue;                  // 4방 탐색                 for (int d = 0; d < 4; d++) {                     int xx = now.x + dx[d];                     int yy = now.y + dy[d];                     // 범위를 벗어날 경우, 호수가 있을 경우 pass                     if(xx < 0 || yy < 0 || xx >= N || yy >= M || map[xx][yy] == 0) continue;                     // 이미 같은 배양액이 뿌려져 있다면 pass                     if(visitedGrn[xx][yy] != 0) continue;                       // 초록색 배양액이 뿌려진 적이 없다면 퍼진다                     visitedGrn[xx][yy] = visitedGrn[now.x][now.y] + 1;                     green.add(new State(xx, yy, now.color));                 }             }                          // 다음으로 빨간색 배양액부터 퍼진다.                         size = red.size();             for (int s = 0; s < size; s++) {                 State now = red.poll();                                  // 4방 탐색                 for (int d = 0; d < 4; d++) {                     int xx = now.x + dx[d];                     int yy = now.y + dy[d];                     // 범위를 벗어날 경우, 호수가 있을 경우 pass                     if(xx < 0 || yy < 0 || xx >= N || yy >= M || map[xx][yy] == 0) continue;                     // 이미 같은 배양액이 뿌려져 있다면 pass                     if(visitedRed[xx][yy] != 0) continue;                                          visitedRed[xx][yy] = visitedRed[now.x][now.y] + 1;                                          // 초록색 배양액이 동일한 시간대에 뿌려졌다면 꽃이 핀다.                     if(visitedGrn[xx][yy] == visitedRed[xx][yy]) {                         cnt++;                         // 꽃이 핀 자리는 -100 저장                          visitedGrn[xx][yy] = -100;                         visitedRed[xx][yy] = -100;                         continue;                     }                                          // 그 외의 경우는 배양액이 퍼진다                     red.add(new State(xx, yy, now.color));                 }             }         }           return cnt;     } } Colored by Color Scripter

cs