1. 문제 설명
- 문제 링크
연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다.
조건
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
2. 풀이
- bfs를 활용하여 구역나누기
- bfs의 실행횟수로 단지의 갯수 파악 가능
- bfs 내부에서 단지내 집의 수 파악 가능
3. 코드
- c++
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int a[30][30];
int group[30][30];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int n;
int ans[25*25];
void bfs(int x, int y, int cnt) {
queue<pair<int,int>> q;
q.push(make_pair(x,y));
group[x][y] = cnt;
while (!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
for (int k=0; k<4; k++) {
int nx = x+dx[k];
int ny = y+dy[k];
if (0 <= nx && nx < n && 0 <= ny && ny < n) {
if (a[nx][ny] == 1 && group[nx][ny] == 0) {
q.push(make_pair(nx,ny));
group[nx][ny] = cnt;
}
}
}
}
}
int main() {
scanf("%d",&n);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
scanf("%1d",&a[i][j]);
}
}
int cnt = 0;
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
if (a[i][j] == 1 && group[i][j] == 0) {
bfs(i, j, ++cnt);
}
}
}
printf("%d\n",cnt);
for (int i=0; i<n; i++) {
for (int j=0; j<n; j++) {
ans[group[i][j]]+=1;
}
}
sort(ans+1, ans+cnt+1);
for (int i=1; i<=cnt; i++) {
printf("%d\n",ans[i]);
}
return 0;
}
- python
from collections import deque
n = int(input())
# 집 유무 및 그룹 정보
map = [list(map(int,list(input()))) for _ in range(n)]
group = [[0]*n]*n
# 탐색 방향
dx = [0,0,1,-1]
dy = [1,-1,0,0]
ans = []
# 모든 칸 탐색
group_num = 1
for i in range(n):
for j in range(n):
# 집이 있고, 그룹에 속하지 않았으면 bfs로 해당 단지 그룹핑
if map[i][j] == 1 and group[i][j] == 0:
cnt = bfs(i, j, group_num, group)
ans.append(cnt)
group_num += 1
def bfs(x, y, group_num, group):
deq = deque()
deq.appendleft((x, y))
group[x][y] = group_num
cnt = 0
while deq:
x, y = deq.popleft()
cnt += 1
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if 0 <= nx and nx < n and 0 <= ny and ny < n:
if map[nx][ny] == 1 and group[nx][ny] == 0:
deq.appendleft((nx, ny))
group[nx][ny] = group_num
return cnt
# 총 단지 수 출력
print(len(ans))
# 정렬
ans = sorted(ans)
# 출력
for i in range(len(ans)):
print(ans[i])
4. 결과
대표적인 BFS로 영역을 구분하는 문제!