[백준] 2468 안전영역

www.acmicpc.net/problem/2468

2468번: 안전 영역

주어지는 것은 지역의 높이 정보이고, 내리는 비의 양은 6이다. 즉 6 이하의 높이를 가지고 있는 곳은 물에 잠기게 된다.

(입력이 N밖에 주어지지 않았으므로 혹시 다른 문제에서 비의 양이 주어지면 값만 바꿔주면 된다.)

구해야하는 건 안전한 영역의 개수이다. dfs나 bfs를 사용하면 쉽게 구할수 있을 것이다.

DFS나 BFS를 사용해서 구할수 있는 방법은 두가지 인데, 첫 번째는 물에 잠기는 영역을 만들고 안전영역을 구하는 것이고, 두번째는 안전영역을 처음부터 구하는것이다.

첫번째 방법으로는 물에 잠기는 영역을 표시하고, 안전영역을 구해야하므로 불필요한 계산이 있을것이라 생각한다.

그래서 두번째 방법으로 구하였다.

---

테스트케이스의 값이 계속 달라서 문제를 다시보니 안전영역의 최댓값을 찾는 문제였다. 즉, 내리는 비의 양에 따른 모든 경우를 다 조사해야한다.

비의 양이 가장 적을때, 가장 클때의 값을 구했고, for문을 돌려가면서 그 값 마다 생기는 안전 영역을 구해서 가장 큰값만 저장하였다.

다 한줄 알았는데 제출하였을때, 안되었다. 힌트를 보니 아무 지역도 물에 잠기지 않을 수도 있다고 되어있어서 max_val의 값을 1로 초기화해서 비교했더니 성공.

from collections import deque

n = int(input())
area = []
min_rain, max_rain = 100, 0
for _ in range(n):
    tmp = list(map(int, input().split()))
    area.append(tmp)
    min_tmp, max_tmp = min(tmp), max(tmp)
    if max_rain < max_tmp:
        max_rain = max_tmp
    if min_rain > min_tmp:
        min_rain = min_tmp

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(x, y, rain): # x,y = r,c
    q = deque()
    q.append((x, y))
    visit[x][y] = 1
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                if visit[nx][ny]: continue
                if area[nx][ny] <= rain: continue
                q.append((nx, ny))
                visit[nx][ny] = 1

max_val = 1
for _rain in range(min_rain, max_rain + 1):
    visit = [[0] * n for _ in range(n)]
    result = 0
    for i in range(n):
        for j in range(n):
            if visit[i][j]: continue
            if area[i][j] > _rain:
                result += 1
                bfs(i, j, _rain)
                if max_val < result:
                    max_val = result

print(max_val)