백준 18809 Gaaaaaaaaaarden

작성일 | In |

Problem : Gaaaaaaaaaarden

유형 : 조합, 구현, 완전 탐색

해결 전략

  • 주어진 모든 배양액을 남김없이 사용해야 한다 이 조건을 캐치해야 한다. 조합
  • 배양액을 뿌릴 수 있는 땅을 1차적으로 선별하고 permutation을 이용하여, 배양액을 놓을 수 있는 땅의 모든 조합을 만든다.
  • 비슷한 방법으로 푼 문제 : 소문난 칠공주
  • 배양액을 심는 좌표들을 시작점으로 삼고 BFS를 진행 시킨다. BFS 시작점은 여러개가 될 수 있다

주의할 점

  • 배양액마다 따로 BFS를 진행시켜선 안된다.
    • 나의 경우 처음 접근할때, 배양액 별로 따로 진행시키고 접근 시간의 교집합을 이용했다. * 이 방법은 반례가 존재한다.

반례

1
2
2 R 1
G 1 1
  • {1, 1} 지점에 꽃이 피어서 {1, 2} 지점에는 꽃이 피어선 안되지만
  • G 를 먼저 BFS를 진행시킨뒤, R을 BFS를 진행시킨다면
    • {1, 2} 지점에도 꽃이 피게 된다.

풀이

배양액을 심을 수 있는 땅의 좌표를 저장한다

  • 배양액을 심을 수 있는 조합을 이용할때 사용한다.

배양액을 심는 모든 조합을 만들어본다.

  • 초록색 배양액의 경우 4
  • 빨간색 배양액의 경우 3
  • 배양액을 심을 수 있는 좌표가 더 남아있다면 0으로 채워준다.

만약 초록 배양액이 2개, 빨간색 배양액이 3개, 배양액을 심을수 있는 좌표가 7개라면

  • 4433300 이 될것이다.
  • permutation 을 이용하여 모든 조합을 만들어본다.

BFS를 진행한다.

  • 심어진 배양액의 타입을 기록하며, BFS를 진행한다.
  • 주위에 호수가 아니고, 배양액이 퍼져 나갈 수 있는 곳이라면
    • 해당 좌표에 방문한 시간과 자신의 타입을 기록하며 진행한다.
  • 방문하려는곳에 다른 타입의 배양액이 뿌려져 있다면
    • 같은 시간에 방문하는 경우라면 꽃을 피운다.

코드

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
#include <bits/stdc++.h>
#define pp pair<int,int>
#define x first
#define y second
using namespace std;
struct planted {
    int xx, yy;
    int type;
};

int garden[52][52];
int dist[52][52];

queue<planted> q;
vector<pp> can_plant;
vector<int> plant_spot;

int n, m, G, R;

const int dx[] = { -1,1,0,0 };
const int dy[] = { 0,0,-1,1 };

const int lake = 0;
const int flower = 5;
int answer;

int bfs() {
    int flower_cnt = 0;
    while (!q.empty()) {
        auto cur = q.front(); q.pop();

        if (garden[cur.xx][cur.yy] == flower)continue;
        for (int dir = 0; dir < 4; ++dir) {
            int nx = cur.xx + dx[dir];
            int ny = cur.yy + dy[dir];

            if (nx < 0 or nx >= n or ny < 0 or ny >= m)continue;
            int next_type = garden[nx][ny];

            if (next_type == lake or next_type == flower or next_type == cur.type)continue;
            if (next_type == 1 or next_type == 2) {
                garden[nx][ny] = cur.type;
                dist[nx][ny] = dist[cur.xx][cur.yy] + 1;
                q.push({ nx,ny,cur.type });
            }
            else {
                if (dist[nx][ny] != dist[cur.xx][cur.yy] + 1)continue;
                garden[nx][ny] = flower;
                flower_cnt++;
            }
        }
    }
    return flower_cnt;
}

void make_combi() {
    for (int G_seed = 0; G_seed < G; ++G_seed)
        plant_spot.push_back(4);

    for (int R_seed = 0; R_seed < R; ++R_seed)
        plant_spot.push_back(3);

    int left_spot_num = (int)can_plant.size() - G - R;

    for (int i = 0; i < left_spot_num; ++i)
        plant_spot.push_back(0);
}

void solve() {
    make_combi();
    int backup_garden[52][52];
    memcpy(backup_garden, garden, sizeof(garden));

    do {
        memset(dist, -1, sizeof(dist));

        for(int i = 0; i < (int)plant_spot.size(); ++i){

            if (plant_spot[i] == 4) {
                int nx = can_plant[i].x;
                int ny = can_plant[i].y;

                dist[nx][ny] = 0;
                garden[nx][ny] = 4;
                q.push({ nx,ny,4 });
            }
            else if (plant_spot[i] == 3) {
                int nx = can_plant[i].x;
                int ny = can_plant[i].y;

                dist[nx][ny] = 0;
                garden[nx][ny] = 3;
                q.push({ nx,ny,3 });
            }
        }

        answer = max(answer, bfs());
        memcpy(garden, backup_garden, sizeof(garden));

    } while (next_permutation(plant_spot.rbegin(), plant_spot.rend()));

    cout << answer << "\n";
}

void input() {
	cin >> n >> m >> G >> R;

	for (int i = 0; i < n; ++i) {
		for (int ii = 0; ii < m; ++ii) {
			cin >> garden[i][ii];
			if (garden[i][ii] == 2) can_plant.push_back({ i,ii });
		}
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);
    
    input();
    solve();
    return 0;
}

피드백

  • 두개 이상의 좌표에서 BFS를 진행하는 문제를 주의하자.
  • 맨 처음 배양액을 뿌릴때, 좌표에 타입 표시를 안해두고 BFS를 진행하여 답이 이상하게 나왔었다.