소스코드
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")
Python
복사
풀이
DFS 함수의 로직
•
현재 x,y 좌표 방문처리
•
다음으로 이동할 지점을 계산
◦
만약 안전지역이고 방문한 적 없다면 재귀함수를 실행해 DFS 수행
DFS 함수 바깥 부분
•
모든 빗물 높이에서 안전 지역이 몇 개인지 확인해야합니다(모든 경우를 고려해야하므로)
◦
매 빗물 높이에서 사용할 visited(방문 여부 확인용) 2차원 배열을 생성합니다
•
행렬의 모든 부분을 탐색합니다
◦
만약 현재의 장마 수위보다 높은 지역이고 방문한 적 없다면 DFS 시작
◦
안전지역 개수 추가(DFS 첫 시작 == 안전 지역 시작 지점)