백준 온라인 저지의 2667번 단지번호 붙이기 문제입니다.
[링크] https://www.acmicpc.net/problem/2667
문제 조건과 설명
- 정사각형 모양의 지도가 있습니다. 1은 집이 있는 곳, 0은 집이 없는 곳을 나타냅니다.
- 집들로 연결된 모임(좌우 혹은 아래위로 다른 집이 있는 경우 연결되었다고 함)을 단지 하나로 정의하고, 그 단지를 구하고자 합니다.
- 주어진 행렬에서 단지 수와 그 단지 내에 속하는 집의 숫자를 구해야 합니다.
- 위 그림에서 색칠된 구역들이 각각 단지입니다.
- 단지 수는 4개, 각 단지에 속한 집의 수는 시계방향으로 각각 3, 4, 6, 5 입니다.
Input
첫째 줄에는 정사각형 지도의 가로의 크기 N(5<=N<=25)이 주어집니다.
그 다음 N줄에는 각각 N개의 자료 0 혹은 1) 가 주어집니다.
Output
첫째 줄에 총 단지 수, 그리고 각 단지내 집의 수를 오름차순 정렬하여 한 줄마다 출력합니다.
생각한 아이디어
BFS나 DFS로 풀 수 있는 대표적인 문제라고 합니다. 이러한 형태로 갖춘 유사한 문제들이 백준에 많습니다.
여기서는 BFS로 풀어보겠습니다.
- 첫 인덱스부터 차례로 시작하되, 그 위치에서 인접한 위치들을 보고 인덱스를 큐에 push합니다.
- 단, 값이 1이고 방문하지 않은 곳의 경우에만 push 합니다.
- 큐에 요소가 empty가 될 때까지, 큐에 있는 것을 pop 하여 그 위치를 탐색하고 집의 수를 카운트해 줍니다.
단, 이미 방문한 위치는 갈 필요가 없으므로 visit 배열을 활용합니다.
- 코딩에서는 STL의 queue를 활용하였고, pair를 이용하여 열번호 및 행번호를 한 쌍으로 저장해 두었습니다.
소스코드
- DFS로 풀 때는 문제가 없었는데, BFS로 푸니 백준 저지에서 메모리 초과가 떴습니다.
- 이유를 확인해 보니, 큐에 push할 때 visit 체크를 해 주어야 중복 방문이 일어나지 않고 메모리 초과가 뜨지 않는데, 처음 구현할 때에는 큐에서 pop할 때 visit 체크를 했기 때문입니다.
- 맨 위 왼쪽에 있는 1에서 시작하면 큐에는 (1)오른쪽 1과 (2)아래쪽 1이 들어갑니다.
- (1)이, 아래에 있는 1을 방문하여 큐에 넣습니다.
- (2)가, 오른쪽에 있는 1을 방문했습니다.
- 즉 진하게 칠해진 칸은 위에서 중복으로 넣게 됩니다. 그래서 메모리 초과가 났던 것입니다.
- 이를 막기 위해서는 큐에서 빼낸 뒤 그 위치를 방문했는지 보는 것이 아니고, 그 위치에서 인접한 곳들을 push할 때 visit 확인 및 설정을 해야 합니다.
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
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int arr[25][25];
int visit[25][25];
int dy[4] = {-1,1,0,0}; // 상하좌우
int dx[4] = { 0,0,-1,1 };
vector <int> v;
queue <pair<int, int>> q;
void bfs(int iy, int ix, int N) {
int count = 0;
count += 1;
q.push({ iy,ix });
while (!q.empty()) {
int idy = q.front().first;
int idx = q.front().second;
visit[idy][idx] = 1;
q.pop();
for (int k = 0; k < 4; k++) {
int ty = idy + dy[k];
int tx = idx + dx[k];
if (ty < N && ty >= 0 && tx < N && tx >= 0
&& arr[ty][tx] == 1 && visit[ty][tx] == 0) {
q.push({ ty, tx });
visit[ty][tx] = 1;
count += 1;
}
}
}
v.push_back(count);
count = 0;
}
int main() {
int N;
int count = 0;
int iy, ix;
int ty, tx;
scanf("%d", &N);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%1d", &arr[i][j]);
}
}
for (int row = 0; row < N; row++) {
for (int col = 0; col < N; col++) {
if (arr[row][col] == 1 && visit[row][col] == 0) {
bfs(row, col, N);
}
}
}
sort(v.begin(), v.end());
printf("%d\n", v.size());
for (int i = 0; i < v.size(); i++) {
printf("%d\n", v[i]);
}
}