C++)
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#define MAX_NUM 102
using namespace std;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int arr[MAX_NUM][MAX_NUM];
bool visited[MAX_NUM][MAX_NUM];
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
int maxHeight = -987654321;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> arr[i][j];
maxHeight = max(maxHeight, arr[i][j]);
}
}
vector<int> answer;
queue<pair<int, int>> q;
// 가장 높은 지점이 잠기면 어차피 안전영역은 0이므로 검사할 필요가 없다.
for (int height = 0; height < maxHeight; height++) {
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (arr[i][j] <= height || visited[i][j]) continue;
// 안전한 영역을 찾았다.
q.push({ i,j });
visited[i][j] = true;
cnt++;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
if (arr[nx][ny] <= height || visited[nx][ny]) continue;
// 안전한 영역을 찾았다.
q.push({ nx,ny });
visited[nx][ny] = true;
}
}
}
}
answer.push_back(cnt);
for (int i = 0; i < n; i++)
fill(visited[i], visited[i] + n, false);
while (!q.empty())
q.pop();
}
cout << *max_element(answer.begin(), answer.end());
return 0;
}
Python)
import sys
from collections import deque
read = sys.stdin.readline
dx = [1,0,-1,0]
dy = [0,1,0,-1]
n = int(read().rstrip())
arr = [[] * n for _ in range(n)]
visited = [[False] * n for _ in range(n)]
for i in range(n):
arr[i] = list(map(int, read().rstrip().split()))
def bfs(height):
q = deque()
cnt = 0
for i in range(n):
for j in range(n):
if arr[i][j] > height and not visited[i][j]:
visited[i][j] = True
q.append((i,j))
cnt += 1
while q:
x, y = q.popleft()
for k in range(4):
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if arr[nx][ny] > height and not visited[nx][ny]:
visited[nx][ny] = True
q.append((nx,ny))
return cnt
ans = 0
# 비가 안 올수도 있다
for i in range(100 + 1):
temp = bfs(i)
# return이 0이면 최고 높이에 도달해 모든 지역이 잠겼다는 뜻이므로 더이상 검사할 필요가 없다
if temp == 0:
break
ans = max(ans, temp)
visited = [[False] * n for _ in range(n)]
print(ans)'백준 2 > 그래프' 카테고리의 다른 글
| [백준 10026] 적록색약 (C++/Python) (0) | 2020.12.08 |
|---|---|
| [백준 1743] 음식물 피하기 (0) | 2020.12.08 |
| [백준 2583] 영역 구하기 (C++/Python) (0) | 2020.12.08 |
| [백준 1697] 숨바꼭질 (C++/Python) (0) | 2020.12.08 |
| [백준 2606] 바이러스 (C++/Python) (0) | 2020.12.08 |