💡 너비 우선 탐색/깊이 우선 탐색/그래프 이론/그래프 탐색
Memory 2068KB Time 0ms Code Length 1200B
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
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
int N;
char c_map[100][101];
struct loc {
int y, x;
};
void init() {
cin >> N;
for (int i = 0; i < N; i++) {
cin >> c_map[i];
}
}
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,-1,0,1 };
int visited[100][100] = { 0 };
int cnt[2] = { 0 };
void bfs(int idx) {
memset(visited, 0, sizeof(visited));
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[i][j] == 1)continue;
queue<loc> q;
char now_color = c_map[i][j];
q.push({ i,j });
visited[i][j] = 1;
cnt[idx]++;
while (!q.empty()) {
loc 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 >= N || nx >= N || ny < 0 || nx < 0) continue;
if (visited[ny][nx] == 1) continue;
if (c_map[ny][nx] != now_color) continue;
visited[ny][nx] = 1;
q.push({ ny,nx });
}
}
}
}
}
int main() {
init();
bfs(0);
for (int i = 0; i < N; i++) { // 빨간색을 초록색으로 통일
for (int j = 0; j < N; j++) {
if (c_map[i][j] == 'R') {
c_map[i][j] = 'G';
}
}
}
bfs(1);
cout << cnt[0] << " " << cnt[1];
}
이 코드는 N*N 크기의 맵에서 같은 색으로 이어진 영역의 개수를 구하는 프로그램이다.
init 함수에서는 맵의 크기 N과 각 칸의 색 정보를 입력받는다.
bfs 함수는 같은 색으로 이어진 영역의 개수를 구하는 함수이다.
- visited 배열을 초기화하고, 모든 칸을 탐색하면서 방문하지 않은 칸을 찾으면 해당 영역을 bfs로 탐색한다.
- 같은 색깔의 영역을 모두 방문 처리하고, cnt 배열을 이용하여 영역의 개수를 센다.
main 함수에서는 먼저 bfs 함수를 호출하여 빨간색과 초록색 영역의 개수를 구한다.
그 후, 모든 빨간색을 초록색으로 바꾼 뒤 다시 bfs 함수를 호출하여 초록색 영역의 개수를 구한다.
마지막으로, cnt 배열에 저장된 빨간색과 초록색 영역의 개수를 출력한다.
