소스코드

import sys
sys.setrecursionlimit(10000) # 재귀 깊이 제한을 늘리지 않으면 RecursionError 발생
input = sys.stdin.readline

N = int(input().strip())
graph = [list(map(int, input().strip().split())) for _ in range(N)]
MAX_HEIGHT = max(map(max, graph))
result = 0 # 결과값 : 안전지역의 최대 개수

dx = [-1,1,0,0]
dy = [0,0,-1,1]
def dfs(rain_height,visited,x,y):
	visited[x][y] = 1 # 현재 위치 방문 처리
	
	for i in range(4):
		nx = x + dx[i]
		ny = y + dy[i]
		
		if 0 <= nx and 0 <= ny and nx < N and ny < N:
			if graph[nx][ny] > rain_height and visited[nx][ny] == 0:
				dfs(rain_height, visited, nx, ny) # 재귀함수 실행

# 실행
# 1~최대높이까지 빗물 높이 설정해서 반복
for rain_height in range(MAX_HEIGHT+1):
	visited = [[0] * N for _ in range(N)]
	
	for i in range(N):
		for j in range(N):
			# 장마 수위보다 높은 지역이고 방문한 적 없다면 dfs 수행
			if graph[i][j] > rain_height and visited[i][j] == 0:
				dfs(rain_height, visited, i, j)
				result += 1 # 안전지역 개수 추가

# 출력
sys.stdout.write(f"{result}\\n")

풀이

DFS 함수의 로직

• 현재 x,y 좌표 방문처리
• 다음으로 이동할 지점을 계산
  • 만약 안전지역이고 방문한 적 없다면 재귀함수를 실행해 DFS 수행

DFS 함수 바깥 부분

• 모든 빗물 높이에서 안전 지역이 몇 개인지 확인해야합니다(모든 경우를 고려해야하므로)
  • 매 빗물 높이에서 사용할 visited(방문 여부 확인용) 2차원 배열을 생성합니다
• 행렬의 모든 부분을 탐색합니다
  • 만약 현재의 장마 수위보다 높은 지역이고 방문한 적 없다면 DFS 시작
  • 안전지역 개수 추가(DFS 첫 시작 == 안전 지역 시작 지점)