[PS] 문제풀이/백준
[ 백준 1926 ] 그림 (C++)
안산학생
2020. 2. 24. 23:16
[해결과정]
1. input
-> n, m (세로, 가로) 변수, arr (map 2차원 배열)
2. arr 맵을 돌며, arr[i][j]==1 이고, check[i][j]==0 (방문하지않음) 이라면, 진입
-> group(집합 갯수)를 +1 시키고, cnt(원소 갯수)를 1로 초기화한다.
-> ★★★그리고 만약 maxCnt(최대 원소 갯수) 보다 cnt가 크면 maxCnt == cnt;
-> check[i][j]==1로 방문체크를 한다.
-> queue에 i,j좌표를 삽입하고, BFS()로 진입한다.
3. BFS
-> 주변 4방향을 탐색하며, arr[i][j]==1이고, check[i][j]==0 인 곳 진입
-> cnt(원소 갯수)++;
-> 그리고 만약 maxCnt(최대 원소 갯수) 보다 cnt가 크면 maxCnt == cnt;
-> queue에 i,j좌표를 삽입한다.
4. ouput
-> group(집합 갯수) == 0 이면 cnt 또한 0...
-> 위와 같은 경우가 아니라면, group과 cnt 출력.
[소스코드]
|
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
78
79
80
81
82
83
84
|
/*
BOJ 1926 - 그림
Created by haejun on 2020/02/24
*/
#include<iostream>
#include<queue>
#include<memory.h>
using namespace std;
const int MAX = 502;
int arr[MAX][MAX];
int check[MAX][MAX];
int n, m;
struct coor {
int y;
int x;
};
int group;
int cnt;
int maxCnt;
queue <coor> q;
//inside check, dir
bool inside(int y, int x) {
return y >= 0 && y < n && x >= 0 && x < m;
}
int dy[4] = {-1,1,0,0};
int dx[4] = { 0,0,-1,1 };
void bfs() {
while (!q.empty()) {
int y = q.front().y;
int x = q.front().x;
q.pop();
int ny, nx;
for (int i = 0; i < 4; i++) {
ny = y + dy[i];
nx = x + dx[i];
if (inside(ny, nx) && arr[ny][nx] == 1 && check[ny][nx] == 0) {
check[ny][nx] = 1;
cnt++;
if (cnt > maxCnt) maxCnt = cnt;
q.push({ ny,nx });
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> arr[i][j];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (arr[i][j] == 1 && check[i][j]==0) {
check[i][j] = 1;
group++;
cnt = 0;
cnt++;
if (cnt > maxCnt) maxCnt = cnt;
q.push({ i,j });
bfs();
}
}
}
if (group == 0) {
cout << "0\n0";
}
else {
cout << group << "\n";
cout << maxCnt << "\n";
}
return 0;
}
|
[해결 과정 중 실수한 부분]
전형적인 BFS() 문제이다. 기본적인 BFS문제이지만, 2번만에 맞췄다.... 사유는 위에 별표 친 곳! 그 부분을 빠뜨려서, 한 번 틀렸다... 기초적이고 기본적인 문제라고 해서 한 번에 다 맞추는 것은 쉬운 일이 아니다...
[관련 문제 혹은 비슷한 문제]
BFS