[BFS&완전탐색] 백준 2468 안전 영역
2021. 3. 19. 13:56ㆍ알고리즘 문제분석
수행 시간 : 2시간 + 오류수정시간(약 1시간)
난이도 실버 1의 전형적인 bfs를 통해 해결하는 문제였다. 이 문제에서 가장 큰 고민 부분은 과연 구역을 어떻게 나눌 것 인가 였다. 물에 잠기는 땅은 bfs를 통해 visited를 true로 만들어 주면 되는 것인데 구역을 나눌 방법이 떠오르지 않았다. 그런데 생각을 해본 결과 구역을 나누는 방법은 의외로 간단하다. visited가 false이고 map이 홍수 높이 h 보다 크면 자연스럽게 영역이 되는 것이다. 즉,
if (!visited[i][j] && map[i][j] >= a) {
area++;
이 코드를 while(!q.empty()) 들어가기전에 작성해주면 되는 것... 이거 한줄을 고민하기 위해 거의 1시간을 날렸다..ㅜㅜ
전체 코드는
#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
int map[101][101];
bool visited[101][101];
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };
int h = 0;
int bfs(int a) {
int area = 0;
queue<pair<int, int>> q;
memset(visited, 0, sizeof(visited));
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
if (!visited[i][j] && map[i][j] >= a) {
area++;
visited[i][j] = true;
q.push({ i,j });
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0;k < 4;k++) {
int nx = dx[k] + x;
int ny = dy[k] + y;
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
if (visited[nx][ny] == false && map[nx][ny] >= a) {
visited[nx][ny] = true;
q.push({ nx,ny });
}
}
}
}
}
}
}
return area;
}
int main() {
int max_size = 0;
cin >> n;
for (int i = 0;i < n;i++) {
for (int j = 0;j < n;j++) {
cin >> map[i][j];
h = max(h, map[i][j]);
}
}
for (int i = 1;i <= h;i++) {
int ans = bfs(i);
if (max_size < ans) {
max_size = ans;
}
}
cout << max_size;
}
'알고리즘 문제분석' 카테고리의 다른 글
[BFS] 백준 5014 스타트링크 (0) | 2021.03.27 |
---|---|
[구현] 백준 14499 주사위 굴리기 (0) | 2021.03.24 |
[BFS] 백준 1697 숨바꼭질 (0) | 2021.03.16 |
[구현] 백준 17144 미세먼지 안녕! (0) | 2021.03.16 |
[BFS&구현] 백준 16236 아기상어 (0) | 2021.03.16 |