https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 난이도는 실버 1티어 이지만 DFS, BFS의 개념만 정확하게 알고 있으면 쉽게 해결할 수 있는 문제였습니다. 상, 하, 좌, 우 4가지 방향으로 움직일 수 있기 때문에 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1]로 방향 리스트를 생성합니다. 그 후 bfs함수를 구현합니다.
소스코드 - python
|
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
|
from collections import deque
n = int(input())
graph = []
for i in range(n):
graph.append(list(map(int, input())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
ans = []
cnt = 0
def bfs(xPos, yPos):
count = 1
q = deque()
q.append((xPos, yPos))
graph[xPos][yPos] = 0
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < n and 0 <= ny < n:
if graph[nx][ny] == 1:
graph[nx][ny] = 0
q.append((nx, ny))
count += 1
ans.append(count)
for i in range(n):
for j in range(n):
if graph[i][j] == 1:
bfs(i, j)
cnt += 1
ans.sort()
print(cnt)
for i in ans:
print(i)
|
cs |
소스코드 - c++
|
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 <bits/stdc++.h>
#define MAX 26
using namespace std;
int graph[MAX][MAX];
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
bool visited[MAX][MAX];
vector<int> vec;
void bfs(int xPos, int yPos, int n) {
queue<pair<int, int>> q;
q.push({ xPos, yPos });
int count = 1;
visited[xPos][yPos] = true;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || ny < 0 || nx >= n or ny >= n)
continue;
if (graph[nx][ny] != 0 && visited[nx][ny] == false) {
q.push({ nx, ny });
count += 1;
visited[nx][ny] = true;
}
}
}
vec.push_back(count);
}
int main(void) {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf("%1d", &graph[i][j]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (graph[i][j] != 0 && visited[i][j] == false) {
bfs(i, j, n);
}
}
}
sort(vec.begin(), vec.end());
printf("%d\n", vec.size());
for (int i = 0; i < vec.size(); i++) {
printf("%d\n", vec[i]);
}
return 0;
}
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 15903: 카드 합체 놀이(Python) (0) | 2021.01.25 |
|---|---|
| 백준 알고리즘 2606: 바이러스(Python) (0) | 2021.01.25 |
| 백준 알고리즘 2178: 미로 탐색 (Python) (0) | 2021.01.19 |
| 백준 알고리즘 1260: DFS와 BFS (Python) (0) | 2021.01.19 |
| 백준 알고리즘 2810: 컵홀더 (Python) (0) | 2021.01.19 |