알고리즘 - Python / 백준 - 2468번 : 안전 영역

2468번: 안전 영역 (acmicpc.net)

2468번: 안전 영역

 

---

풀이

• n * n 격자에 지역의 높이가 입력되고 , 해당 지역에 비가 내렸을 때 높이가 비의 양보다 낮다면 물에 잠긴다.
• 이때 , 만들어질 수 있는 최대 안전지역의 개수를 찾는 문제다.
• 단순하게 그래프 탐색 문제로 풀 수 있다.
• dfs를 이용해서 구현하였고 , 가장 높은 지역보다 비가 더 많이 내린다면 측정할 필요도 없이 모두 물에 잠기기에 최대 높이를 구해주고 0 ~ max 값까지 for문을 통해 해당 비의 양에 따라 dfs를 진행한다.
• 전체 배열을 돌면서 비의 양보다 높이가 낮거나 같다면 넘어가고 , dfs를 진행하면서도 높이를 측정해 낮으면 stack에 추가하지 않는 방식으로 구현하였다.

 

import sys
stack = []; maxx = []
n = int(sys.stdin.readline())
stack.append([-1 for k in range(n+2)])
for _ in range(n):
    pp = list(map(int , sys.stdin.readline().split(" ")))
    maxx.append(max(pp))
    stack.append([-1] + pp + [-1])
stack.append([-1 for k in range(n+2)])
real_max = max(maxx)

def dfs(x,y,level):
    global visited
    global stack
    root = [[x,y]]
    fx = [1,-1,0,0]
    fy = [0,0,1,-1]
    while root:
        node = root.pop(-1)
        if visited[node[0]][node[1]] == 0:
            visited[node[0]][node[1]] = 1
            for p in range(0,4):
                if stack[node[0]+fx[p]][node[1]+fy[p]] > level:
                    root.append([node[0]+fx[p],node[1]+fy[p]])
    return 1

real_ans = 0
for i in range(0,real_max):
    ans = 0
    visited = [[0 for i in range(n+2)] for k in range(n+2)]
    for x in range(1,n+1):
        for y in range(1,n+1):
            if visited[x][y] == 0 and stack[x][y] > i:
                ans += dfs(x,y,i)
    if real_ans < ans:
        real_ans = ans
print(real_ans)

---