💡 너비 우선 탐색/그래프 이론/그래프 탐색/구현/시뮬레이션
Memory 2048KB Time 432ms Code Length 1593B
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
#include<iostream>
#include<queue>
#include<string.h>
using namespace std;
struct info {
int y, x;
};
int N, M;
int result;
char map[50][50];
int visited [50][50];
int successed_visited[50][50];
void init() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
cin >> map[i];
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
map[i][j] -= '0';
}
}
result = 0;
}
int bfs(int y, int x, int max_height) {
memset(visited, 0, sizeof(visited));
memcpy(visited, successed_visited, sizeof(visited));
const int dy[] = {-1,1,0,0};
const int dx[] = {0,0,-1,1};
int sum = 0;
queue<info> q;
q.push({y,x});
visited[y][x] = 1;
sum += (max_height - map[y][x]);
while (!q.empty()) {
info now = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int ny = now.y + dy[i];
int nx = now.x + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= M) return 0; // 수영장 못만들면 아예 종료 시켜버림
if (visited[ny][nx] == 1) continue;
if (map[ny][nx] >= max_height) continue;
visited[ny][nx] = 1;
q.push({ ny,nx });
sum += (max_height - map[ny][nx]);
}
}
memcpy(successed_visited, visited, sizeof(visited));
return sum; // 결과 값이 나왔다면 방문한 곳 visited 고정 처리
}
void solve() {
for (int max_height = 9; max_height > 1; max_height--) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (successed_visited[i][j] == 1) continue;
if (map[i][j] >= max_height) continue;
int tmp_sum = bfs(i,j,max_height);
result += tmp_sum;
}
}
}
cout << result;
}
int main() {
init();
solve();
}
이 코드는 높이가 다른 지형을 가지고 있는 지도에서 주어진 높이 이하의 수영장을 만들었을 때, 수영장의 깊이 합을 구하는 프로그램이다.
init() 함수에서는 지도의 크기를 입력받고, 각 지점의 높이를 정수로 변환하여 저장한다.
bfs() 함수는 너비 우선 탐색을 이용하여 주어진 높이 이하의 지점을 방문하면서 깊이의 합을 계산한다.
solve() 함수에서는 가능한 모든 높이에 대해 각 지점을 시작점으로 하여 bfs()를 호출하여 깊이의 합을 구하고, 결과를 누적한다.
main() 함수에서는 초기화를 수행한 뒤 solve()를 호출하여 결과를 출력한다.
