백준 (boj) 파이썬 - 2468번: 안전영역

#문제링크 :https://www.acmicpc.net/problem/2468

2468번: 안전 영역

#난이도 : Silver1

 

#분류 : DFS

 

#접근방법

DFS를 통해 수심보다 낮은 지역을 0으로 바꾸고, 그 이외의 지역이 몇개의 범위가 되는지 확인한다. 이때 수심을 가장 낮은 지역 ~ 가장 높은 지역을 범위로 +1씩 증가시키며 모두 확인해본다.

문제에서 물에 잠기지 않을수도 있다 라는 조건을 걸었으므로, 정답을 담은 배열에는 1을 하나 넣어준다. (답이 될 수 있는 최소값이 1이므로)

 

Code(Python)

from sys import setrecursionlimit
setrecursionlimit(10000)
n = int(input())

grid = []
cnt = 0
visited = [[False for i in range(n)] for i in range(n)]
for _ in range(n):
    grid.append(list(map(int, input().split())))



def is_valid(x,y):
    if x >= 0 and x < n and y < n and y >= 0:
        return True
    return False

def dfs(x,y):
    if not is_valid(x,y):
        return False
    if visited[x][y] == False and grid[x][y] != 0:
        visited[x][y] = True
        dfs(x+1,y)
        dfs(x-1,y)
        dfs(x,y+1)
        dfs(x,y-1)
        return True
    return False


def rain(depth):
    global visited
    visited = [[False for i in range(n)] for i in range(n)]
    for x in range(n):
        for y in range(n):
            if grid[x][y] <= depth:
                grid[x][y] = 0

min_depth = min(min(grid))
max_depth = max(max(grid))
depth = min_depth
answers = [1]

while(depth <= max_depth):
    rain(depth)
    cnt = 0
    for x in range(n):
        for y in range(n):
            if dfs(x,y):
                cnt += 1

    answers.append(cnt)
    depth += 1
print(max(answers))