문제 URL : https://www.acmicpc.net/problem/15730
15730번: 수영장 사장님
첫째 줄에 N, M(1 ≤ N, M ≤ 100)가 주어진다. 다음 N 줄동안 매 줄마다 M개의 H(0 ≤ H ≤ 10,000)가 주어진다. 여기서 i 번째 줄의 j 번째 정수를 H[i][j] 라고 할 때, H[i][j]는 해당하는 땅의 높이이다.
www.acmicpc.net
문제접근법 : 사면체의 도형들을 입력대로 배치했을때 물이 고일수있는 부분만 확인하는 문제입니다.
여러가지 접근방법이 있지만 가장빠른방법은 그저 물일 고일때까지 물을 부어보는것입니다.
하지만 저는 처음풀었을때 bfs로 물을 부었지만 생각보다 느리더군요
우선 bfs를 이용할때 1부터 입력받은 값중 가장큰값까지 물을 부어봅니다.
즉 h만큼을 해당 물을 외부에서 부었을때 좌우상하 h보다 작은값은 h로 만들어주고 만들지 못한h보다 작은값은 물을 1칸씩 더해주면 서 풉니다.
소스코드 :
|
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
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
int n, m;
int board[102][102];
int hmax = 0;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
void input() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> board[i][j];
hmax = max(board[i][j], hmax);
}
}
}
bool isrange(int y, int x) {
return 0 <= y && y <= n+1 && 0 <= x && x <= m + 1;
}
int bfs(int h) {
int res = 0;
queue<pair<int, int>> q;
q.push({ 0,0 });
board[0][0] = h;
while (!q.empty()) {
int y, x;
tie(y, x) = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (isrange(ny, nx) && board[ny][nx] < h) {
q.push({ ny,nx });
board[ny][nx] = h;
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (board[i][j] < h) {
board[i][j]++;
res++;
}
}
}
return res;
}
void solve() {
int res = 0;
for (int i = 1; i <= hmax; i++) {
res += bfs(i);
}
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
이방법은 h가 1만까지 오르기때문에 bfs를 최대 만번까지돌리는건 매우 비효율적이라 시간이 상당히 느리더군요
시간을 줄여볼 방법을 생각해보면 우선 모든 맵에 무한대로 물을 부어넣습니다.
하지만 맵외부는 반드시 0으로 만듭니다.
그리고 해당 좌우상하와 현재 내자리위치중 가장 작은값과 ,현재 입력받은값중 가장 큰값을 갱신해서
갱신이 안될때까지 만듭니다.
소스코드 :
|
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
|
//By 콩순이냉장고
#include<bits/stdc++.h>
using namespace std;
int n, m;
int hmax = 0;
int dy[4] = { -1,0,1,0 };
int dx[4] = { 0,1,0,-1 };
vector<vector<int>> adj,board;
void input() {
cin >> n >> m;
adj =board= vector<vector<int>>(n + 2, vector<int>(m + 2));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> board[i][j];
adj[i][j] = 1e8;
}
}
}
void solve() {
int res = 0;
while (true) {
bool flag = true;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (board[i][j] == adj[i][j])continue;
int Min = 1e8;
for (int k = 0; k < 4; k++) {
int ny = i + dy[k];
int nx = j + dx[k];
Min = min(Min, adj[ny][nx]);
}
if (adj[i][j]>Min) {
adj[i][j] = max(board[i][j], Min);
flag = false;
}
}
}
if (flag)break;
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
res += adj[i][j] - board[i][j];
cout << res << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는 점 어떤 질문이든 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 1007 벡터 매칭 (1) | 2022.11.01 |
|---|---|
| 백준 피보나치 수 6 (0) | 2022.10.20 |
| 백준 14554 The Other Way (0) | 2022.08.04 |
| 백준 13911 집 구하기 (0) | 2022.07.31 |
| 백준 19237 어른 상어 (0) | 2022.07.21 |
