[백준 2468] 안전영역 (C++/Python)

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)