99클럽 코테 스터디 4일차 TIL + DFS

https://www.acmicpc.net/problem/2468

# 2468 안전영역
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
graph = []
maxNum = 0 # 입력받은 높이의 최댓값 > 비

for _ in range(n):
    graph.append(list(map(int, input().split())))
    maxNum = max(maxNum, max(graph[-1])) # 각 행을 입력받으며 최댓값 구하기

# 상하좌우
dx = [0,0,-1,1]
dy = [-1,1,0,0]

def dfs(x,y,num): # num은 비가 왔을 때 잠기는 높이
    visited[x][y] = True
    
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        if nx < 0 or nx >= n or ny < 0 or ny >= n:
            continue
        if visited[nx][ny] and graph[nx][ny] <= num: #물에잠김
            continue
        if not visited[nx][ny] and graph[nx][ny] > num: # 방문하지 않았고 물에 잠기지 않음
            visited[nx][ny] = True
            dfs(nx,ny,num)


result = 0
for t in range(maxNum):
    cnt = 0
    visited = [[False]*n for _ in range(n)] # i 증가시키며 비 계산 후 reset 처리

    for i in range(n):
        for j in range(n):
            if graph[i][j] > t and visited[i][j] == False: # 비에 잠기지 않았고 방문X
                dfs(i,j,t)
                cnt += 1
    result = max(result, cnt)
print(result)

• 각 행마다 리스트를 입력 받으며 지점 높이의 max값을 구한다 > maxNum
• maxNum을 기준으로 비가 왔을 때 잠기는 지점 높이를 계산하며 안전 영역의 최대 개수를 구한다.
• 상하좌우를 살피며 상하좌우를 구해야하기 때문에 dfs or bfs 알고리즘을 사용한다.
  • 인덱스 값을 고려하며 방문하지 않았고 물에 잠기지 않을 경우 방문처리를 해주고 dfs함수를 호출한다.
• sys.setrecursionlimit(10**7)은 파이썬을 사용할 때 최대 재귀 깊이를 늘려 제출 시 런타임에러(RecursionError) 를 방지한다.