백준 2468번 : 안전 영역 in Python

2468번: 안전 영역

 

www.acmicpc.net

이 문제는 어떤 지역의 높이 정보가 주어졌을 때, 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 계산하는 문제이다. 여기서 안전한 영역이란 강수량보다 해당 지역의 높이가 더 높아 물에 잠기지 않는 지점들의 집합 중 지점들끼리 서로 인접한 최대 영역을 말한다.

우선 특정 강수량이 주어진 경우를 생각해보자. 그러면 그 강수량에 대한 안전한 영역의 개수를 구하는 문제는 이전의 섬의 개수 문제와 거의 동일하다. 단지 안전한 영역을 찾기 위해 강수량보다 지점의 높이가 더 높은 지점에 대해서만 그래프 탐색을 한다는 점만 다를 뿐이다.

백준 4963번 : 섬의 개수 in Python

4963번: 섬의 개수 www.acmicpc.net 이 문제는 섬과 바다 지도가 주어질 때 섬의 개수를 세는 문제이다. 단, 두 정사각형이 같은 섬에 있기 위해서는 두 정사각형이 가로, 세로 또는 대각선으로 인접하고 있어야..

wanna-be-developer-yjh.tistory.com

하지만 이 문제에서 원하는 값은 모든 강수량에 대한 안전한 영역의 최대 개수이므로, 강수량이 0일 때부터 해당 지역 중 가장 높은 지점의 높이일 때까지의 모든 경우를 고려해 영역의 개수를 센 뒤, 그 중 가장 큰 값을 고르면 될 것이다.

이를 코드로 구현하면 다음과 같다.

import sys
sys.setrecursionlimit(10**5)
def DFS(x, y):
    global h, N
    if visited[x][y]: return
    visited[x][y] = True
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # 강수량보다 더 높은 지점에 대해 DFS를 재귀적으로 호출한다.
        if 0<=next_x<N and 0<=next_y<N and m[next_x][next_y] > h:
            DFS(next_x, next_y)
N = int(input())
m = []
for _ in range(N):
    m.append(list(map(int, input().split())))
# 해당 지역에서 가장 높은 지점의 높이를 찾는다.
max_height = 0
for i in range(N):
    max_height = max(max_height, max(m[i]))
# 모든 가능한 강수량에 대해 가장 많은 안전한 영역의 개수를 저장하는 변수
max_cnt = 0
# 모든 가능한 강수량에 대해 안전한 영역의 개수를 구한다.
for h in range(max_height):
    visited = [[False]*N for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(N):
            if not visited[i][j] and m[i][j] > h:
                DFS(i, j)
                cnt += 1
    max_cnt = max(max_cnt, cnt)
print(max_cnt)