백준 2468. 안전 영역

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

2468번: 안전 영역

import copy
def dfs(sti,stj):
    global cnt, max_cnt
    q=[(sti,stj)]
    arr[sti][stj] = 0
    while q:
        i,j = q.pop(0)
        for ti,tj in [(1,0),(-1,0),(0,1),(0,-1)]:
            ni, nj = i+ti, j+tj
            if 0<=ni<n and 0<=nj<n and arr[ni][nj]>rain: # 유효한 인덱스에 잠기지 않은 구역이라면
                q.append((ni,nj))
                arr[ni][nj] = 0
    cnt += 1
    if max_cnt <= cnt:
        max_cnt = cnt

n = int(input())
arr = [list(map(int,input().split())) for _ in range(n)]
copy_arr = copy.deepcopy(arr)   # 비 양이 늘어날 때마다 arr을 원상복구 해주기위해
cnt, max_cnt = 0,0  # 구역 개수/최대구역개수
rain = 0    # 비의 양
while True:
    flag = 0
    for i in range(n):
        for j in range(n):
            if arr[i][j] > rain:    # arr에서 잠기지 않은 곳 기준으로 dfs돌리기
                flag = 1
                dfs(i,j)
    if flag == 1:   # dfs를 돌릴게 있었으면(안전구역이 하나라도 있으면)
        rain += 1   # 비 양을 늘려 다시 while문을 돌린다
        cnt = 0     # cnt도 초기화 시켜줌
        arr = copy.deepcopy(copy_arr)   # arr도 원상복구 시켜줌
    else:   # 모두 잠긴다면?
        break   # 비 양을 늘려볼 필요 없이 끝내기
print(max_cnt)

단지번호 문제와 유사하게 visited을 따로 만들지 않고 풀기!