2468_안전 영역

문제

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

2468번: 안전 영역

 

접근 방식 

1. 상하좌우를 돌며 내린 비의 양보다 높은 곳이 있는지 파악한다 -> DFS 활용 

2. 높다면 방문처리 한 뒤 return True 

3. 낮다면 return False 

이 과정을 가장 높은 지역 크기 만큼 반복 (내리는 비의 양)

 

주의할 점 

1. 재귀 함수 범위에 주의하자 

# 재귀 함수 범위를 늘려주는 코드 
import sys
sys.setrecursionlimit(10**7)

2. 제공된 graph를 사용하여 방문처리를 하는 것보단 새로운 방문 배열을 만들어 활용하자 

graph를 복사하는 방향으로 처리하는 것 보다 간편하다 

 

3. 확인할 비의 양의 범위를 (가장 낮은 지대 ~ 가장 높은 지대 + 1)으로 지정한다면 

가장 낮은 지대보다 적은 양의 비가 내렸을 때를 판단할 수없다 -> (0 ~ 가장 높은 지대 + 1)의 범위로 돌리자! 

 

정답 코드 

# 재귀함수 범위 늘리기
import sys
sys.setrecursionlimit(10**7)

n = int(input())
graph = []
for _ in range(n):
    graph.append(list(map(int, input().split())))

res = []

# 상하좌우돌며 제시된 값보다 큰 연결된 지역 확인
def dfs(x, y, rain, visited):
    # 예외처리
    if x < 0 or x >= n or y < 0 or y >= n:
        return False

    # 상하좌우 돌기
    if graph[x][y] > rain and visited[x][y] == False:
        # 방문처리
        visited[x][y] = True
        dfs(x, y - 1, rain, visited)
        dfs(x, y + 1, rain, visited)
        dfs(x - 1, y, rain, visited)
        dfs(x + 1, y, rain, visited)
        return True
    return False

maximun = max(map(max, graph))
# minimum = min(map(min, graph))

    # minimum 부터 반복하면 minimum 보다 작은 값일 때 판단할 수 없음
# for k in range(minimum, maximun + 1):
for rain in range(maximun + 1):
    visited = [([False] * (n + 1)) for _ in range(n + 1)]
    cnt = 0
    for i in range(n):
        for j in range(n):
            if dfs(i, j, rain, visited):
                cnt += 1
    res.append(cnt)

print(max(res))