[bfs/백준] 2468번 : 안전 영역

- 문제 : https://www.acmicpc.net/problem/2468

 

문제 이해

- 비가 h가 높이만큼 오면 높이가 h 이하인 건물은 물에 잠기는데, 잠기지 않는 영역(비 높이 < 건물 높이)을 구하는 문제다. 

- 비의 높이가 따로 주어지지 않았으므로 비가 오는 높이의 모든 경우의 수를 고려해야한다. (비가 오지 않는 높이 0부터 건물의 최대 높이까지 진행한다)

- 비 높이 초과인 건물들의 영역을 구하면 그게 안전영역이므로 bfs를 1번만 진행한다. (비가 와서 잠긴 영역을 처리하고, 잠기지 않은 영역을 bfs로 구하면 bfs를 중복으로 연산하므로 효율적이지 않기 때문)

풀이 로직

- 건물 높이 정보를 입력받는다. 이때 건물의 최대 높이를 max_height 변수에 저장한다. rain은 비가 오는 높이다. 

- 비가 오지 않는 경우(rain == 0) 부터 최대로 오는 경우(rain == max_height)까지 반복문을 돌면서 그때마다 bfs를 진행한다.

- 방문하지 않은 지점 중에 잠기지 않는 건물(높이 > rain)이 있다면 그 건물을 중심으로 영역을 탐색한다.

- 각 비가 오는 높이에 따라 잠기지 않는 영역 개수를 temp로 계산한뒤 그때그때마다 최대값을 answer에 저장한다.

- 반복문을 나오면 answer의 값이 최대이자 정답이므로 answer를 출력한다.

 

정답 풀이 

n = int(input())

matrix = []
max_height = 0
for _ in range(n):
    arr = list(map(int, input().split()))
    max_height = max(max_height, max(arr))
    matrix.append(arr)

def bfs(x, y, visit, matrix, rain):
    queue = [[x, y]]
    visit[x][y] = 1
    dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
    while queue:
        x, y = queue.pop(0)
        
        for i in range(4):
            nx, ny = x + dx[i], y + dy[i]
            if 0 <= nx < n and 0 <= ny < n :
                if not visit[nx][ny] and matrix[nx][ny] > rain:
                    visit[nx][ny] = 1
                    queue.append([nx, ny])
        
    
answer = 0   
for rain in range(max_height + 1):
    temp = 0 # rain 높이에도 잠기지 않는 영역 
    visit = [[0] * n for _ in range(n)]
    for x in range(n):
        for y in range(n):
            if not visit[x][y] and matrix[x][y] > rain:
                bfs(x, y, visit, matrix, rain)
                temp += 1                
                
    answer = max(answer, temp)    
    
print(answer)