https://www.acmicpc.net/problem/2468
시간 1초, 메모리 128MB
input :
- N(2 <= N <= 100)
- 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력
output :
- 물에 잠기지 않는 안전한 영역의 최대 개수를 출력
일단 문제의 모든 건물의 높이는 1 ~ 100 사이이다.
그리고 최대로 많은 건물의 개수는 1만개인데, 이 둘을 이용해 시간을 생각해 보았을때 끽해봐야 10만 수준에서 그친다. 고로 그냥 해도 괜찮다.
일단 비가 올수 있는 모든 상황을 가정해야 하는데 여기에는 비가 오지 않는 0부터 ~ 99 까지를 생각하면 될 거 같다. 어차피 100이면 모두 침몰 되니까 안 따져도 될 듯 하다.
그리고 visit을 이용해서 각 건물을 들어갈 수 있는지 확인하고, 비 보다 높은 건물인 경우에만 bfs를 수행한다.
import sys
from collections import deque
def bfs(start_x, start_y, rain):
q = deque([(start_x, start_y)])
visit[start_x][start_y] = 1
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or nx >= n or ny < 0 or ny >= n:
continue
if graph[nx][ny] > rain and visit[nx][ny] == 0:
q.append((nx, ny))
visit[nx][ny] = 1
n = int(sys.stdin.readline())
graph = []
for i in range(n):
graph.append(list(map(int, sys.stdin.readline().split())))
cnt = 0
for rain in range(101):
visit = [[0] * n for i in range(n)]
temp = 0
for x in range(n):
for y in range(n):
if visit[x][y] == 0 and graph[x][y] > rain:
bfs(x, y, rain)
temp += 1
cnt = max(cnt, temp)
print(cnt)
