https://www.acmicpc.net/problem/1926
1926번: 그림
어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로
www.acmicpc.net
풀이
드디어 자료구조를 넘어 Theme.BFS에 진입했다.
이산수학과 자료구조에서 지겹도록 배운 BFS,DFS인데 막상 코드로 짜려니 신경써줘야 할 것이 많았다.
이 문제는 BFS의 기본문제라고 할 수 있겠다.
Flood Fill이라는 idea를 채용한다고 할 수 있겠는데 Flood Fill이란
예를 들어 그림판에서 내가 양동이 아이콘을 클릭하여 어떤 도형 안쪽을 클릭하면 가득 채워짐을 알 수 있다.
그런데 컴퓨터는 어느 범위까지 채워야하는 지 어떻게 알까? 경계까지 탐색을 통해 알 수 있다.
이것을 Flood Fill이라고 칭한다. (출처 : 바킹독https://blog.encrypted.gg/941)
[실전 알고리즘] 0x09강 - BFS
안녕하세요 여러분, 드디어 올 것이 왔습니다. 마음의 준비를 단단히 하셔야 합니다.. 드디어 실전 알고리즘 강의에서 첫 번째 고비에 도달했는데 이 강의와 함께 이번 고비를 잘 헤쳐나가면 좋
blog.encrypted.gg
아무튼, 2D Array를 이용한 BFS의 가장 기본적인 문제로 어떻게 풀 지 떠올릴지는 어렵지 않을 것이다.
하지만 구현이 어렵다..! (Idea는 떠오르는데 구현을 못한다니 난 정말 전공자인가.)
이 문제와 같이 코드로 덤비다가 머리가 복잡해졌었는데 수도 코드를 작성해보니 금방 풀었다. 물론 참고해서
내 코드
#include <bits/stdc++.h>
#define X first
#define Y second
using namespace std;
int board[502][502] = {};
int vis[502][502] = {};
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m, cnt = 0, val = 0;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (!board[i][j] || vis[i][j]) continue;
cnt++;
queue<pair<int, int>> q;
q.push(make_pair(i, j));
vis[i][j] = 1;
int temp = 0;
while (!q.empty()) {
temp++;
pair<int, int> cur = q.front(); q.pop();
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (vis[nx][ny] || !board[nx][ny]) continue;
vis[nx][ny] = 1;
q.push(make_pair(nx, ny));
}
}
val = max(temp, val);
}
}
cout << cnt << '\n' << val;
}
아 pair을 이용하는 것은 이전 stack 문제에서 사용했던 idea이다.
https://developer-dz.tistory.com/81
[C++] 2493번 : 탑
기술하기에 앞서 정말 배운 것이 많은 문제입니다. (STL 中 Pair Class,출력초과,monotonic stack) 풀이 1874번 스택 수열을 풀어보셨다면 접근 자체는 할 수 있었을 것 같습니다. 직관적으로 생각나는 풀
developer-dz.tistory.com
당연히 처음이라 어려운 것이겠지.? 이 코드 형태는 정말 웰 노운 형태라고 하니 정진하자
'Baekjoon' 카테고리의 다른 글
[C++] 7576번 : 토마토 (0) | 2024.03.20 |
---|---|
[C++] 2178번 : 미로탐색 (0) | 2024.03.20 |
[C++] 1021번 : 회전하는 큐 (0) | 2024.03.08 |
[C++] 2164번: 카드2 (0) | 2024.03.07 |
[C++] 10845 : 큐/18258 : 큐2 (1) | 2024.03.06 |