[Algorithm] 백준 BOJ 2468 안전 영역 python 파이썬 그래프 실버 1

Private 난이도 : ♥♥♥♡♡

2468번: 안전 영역

import sys
sys.setrecursionlimit(10000)
def dfs(x, y, water,graph,visited):
    if x < 0 or x >= n or y >= n or y < 0:  # 탈출조건
        return False
    if visited[y][x]==True:
        return False

    if graph[y][x] > water:
        visited[y][x] = True
        dfs(x + 1, y, water,graph,visited)
        dfs(x - 1, y, water,graph,visited)
        dfs(x, y + 1, water,graph,visited)
        dfs(x, y - 1, water,graph,visited)
        return True
    else:
        return False

n = int(sys.stdin.readline().strip()) # 행과 열의 개수
graph=[]
for i in range(n):
    graph_inner = list(map(int, sys.stdin.readline().strip().split()))# 행하나를
    graph.append(graph_inner) #전체 행렬에 append
    # 데이터 받기 끝
# for y in range(n):# 그래프 전체 모양 보기
#         print(graph[y])
highest=max(max(graph)) # 전체 중 최대 높이

result = 1  # 비의 양이 0일 때
for water in range(1,highest):
    visited=[[False]*n for _ in range(n)]
    water_result=0
    for x in range(n):
        for y in range(n):
            if dfs(x, y, water,graph,visited) == True:
                water_result += 1
    if result <= water_result:
        result=water_result
    print(water,'result',result)
print('결과 height',result)

백준 제출 버전

설명

• 각 물의 높이일 떄마다 경우를 다 해야되기 때문에 graph에서 가장 높은 수를 highest로 저장했다
• 비의 양이 0일 때는 무조건 1이고, 비의양=highest일 때는 다 잠기기때문에  0 이다
  그래서 1을 default값으로 두었고 highest는 0이니까 돌리지 않았다
• 현재 그래프의 값이 비의양보다 높아야한다 예를들어 지금 비가 4라면 5부터 안전영역이니까 >로 했었어야했는데 처음에는 헷갈려서 >= 이렇게 했었다. ㅠ